il mio programma funziona per la subtask 2 poi fa molti errori in tutte le altre (stranamente non va in TLE), per scriverlo ho preso spunto da questa guida.
Ecco il codice:
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops")
#define valore_di(x) cerr <<"il valore di "<< #x << " è " << x << endl;
#include <bits/stdc++.h>
#define MAXN 1500000
#define INF numeric_limits<int>::max()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ip;
struct Node{
ll val; //the value for leafs and the min for others (si, mi piace scrivere in inglese)
ll sum; //only non leafs node need this
bool same; //true if every child has the same value
ll add; //the quantity to add to childrens
int childrens;
int index;
Node(){
add=0;
same=false;
childrens=1;
}
};
Node t[4*MAXN];
int n;
void push (int v){
if (t[v].same) {
t[v*2].val = t[v*2+1].val = t[v].val;
t[v*2].sum = t[v].val*t[v*2].childrens; t[v*2+1].sum = t[v].val*t[v*2+1].childrens;
t[v*2].same = t[v*2+1].same = true;
t[v].same = false;
}
else {
t[v*2].add += t[v].add;
t[v*2+1].add += t[v].add;
t[v*2].val += t[v].add;
t[v*2+1].val += t[v].add;
t[v*2].sum += t[v].add*t[v*2].childrens;
t[v*2+1].sum += t[v].add*t[v*2+1].childrens;
t[v].add=0;
}
//cout<<v*2<<" "<<t[v*2].sum<<" "<<t[v*2].add<<" "<<t[v*2].val<<" "<<t[v*2].childrens<<endl;
//cout<<v*2+1<<" "<<t[v*2+1].sum<<" "<<t[v*2+1].add<<" "<<t[v*2+1].val<<" "<<t[v*2+1].childrens<<endl<<endl;
}
void build(vector<ll> &a, int v, int tl, int tr) {
if (tl == tr) {
t[v].val = t[v].sum = a[tl];
t[v].index = tl;
//cout<<v<<" "<<tl<<" "<<tr<<" "<<a[tl]<<endl;
} else {
//cout<<v<<" "<<tl<<" "<<tr<<endl;
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v].val = min(t[v*2].val , t[v*2+1].val);
t[v].sum = t[v*2].sum + t[v*2+1].sum;
t[v].childrens = t[v*2].childrens+t[v*2+1].childrens;
}
}
void init(vector<ll> a) {
n=a.size();
build (a, 1, 0, n-1);
/*for (int i=0; i<n; i++) t[i+n].val = t[i+n].sum = a[i];
for (int i=n-1; i>0; i--){
t[i].val = min(t[i*2].val , t[i*2+1].val);
t[i].sum = t[i*2].sum + t[i*2+1].sum;
t[i].childrens = max(t[i*2].childrens, 1)*2;
}*/
for(int i=1;i<26;i++) cout<<t[i].sum<<" ";cout<<endl;
}
ll sum(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l == tl && r == tr){
if(tl==tr) return t[v].val; //se v è una foglia rirorna val e non sum
return t[v].sum;
}
push(v);
int mid = (tl + tr) / 2;
if(t[v].same)return t[v].val*t[v].childrens; //(r-l) è il numero di nodi figli
return sum(v*2, tl, mid, l, min(r, mid)) + sum(v*2+1, mid+1, tr, max(l, mid+1), r) + t[v].add;
}
long long get_sum(int l, int r) {
return sum(1, 0, n-1, l, r-1);
}
ll addrange(int v, int tl, int tr, int l, int r, int addend) {
if (l > r) return 0;
if (l == tl && tr == r) {
if (!t[v].same) t[v].add += addend;
t[v].val += addend;
t[v].sum += addend*(r-l+1);
return addend*(r-l+1);
} else {
push(v);
int tm = (tl + tr) / 2;
ll x = addrange(v*2, tl, tm, l, min(r, tm), addend);
ll y = addrange(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
t[v].val = min(t[v*2].val, t[v*2+1].val);
t[v].sum += x+y;
//cout<<v<<" "<<x<<" "<<y<<endl;
return x+y;
}
}
void add(int l, int r, long long x) {
addrange(1, 0, n-1, l, r-1, x);
for(int i=1;i<26;i++) cout<<t[i].sum<<" ";cout<<endl;
}
ip setrange(int v, int tl, int tr, int l, int r, int new_val) {
if (l > r) return {0,t[v].val};
//cout<<v<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
if (l == tl && tr == r) {
ll sumT = new_val - t[v].val;
t[v].val = new_val;
t[v].sum = new_val*t[v].childrens;
t[v].same = true;
return {sumT*t[v].childrens , new_val}; //{differenza da aggiungere a sum , valore minimo}
} else {
push(v);
int mid = (tl + tr) / 2;
ip x = setrange(v*2, tl, mid, l, min(r, mid), new_val);
ip y = setrange(v*2+1, mid+1, tr, max(l, mid+1), r, new_val);
t[v].val = min(x.second,y.second);
t[v].sum = t[v*2].sum + t[v*2+1].sum;
//cout<<v<<" "<<x.first<<" "<<y.first<<endl;
return {x.first+y.first, t[v].val};
}
}
void set_range(int l, int r, long long x) {
setrange(1, 0, n-1, l, r-1, x);
//for(int i=1;i<26;i++) cout<<t[i].sum<<" ";cout<<endl;
}
ll getmin(int v, int ll, int rr, int l, int r){
//cout<<v<<" "<<ll<<" "<<rr<<" "<<l<<" "<<r<<endl;
if (l > r) return INF;
//if (l <= ll && rr <= r)cout<<t[v].val<<endl;
if (l <= ll && rr <= r) return t[v].val;
push(v);
int mid = (ll+rr)/2;
return min(getmin(v*2,ll,mid,l,min(r,mid)),getmin(v*2+1,mid+1,rr,max(l,mid+1),r));
}
long long get_min(int l, int r) {
return getmin (1,0,n-1,l,r-1); //controllare n-1
}
int find(int v, int tl, int tr, int l, int r, ll x){ //copia incollata
if(tl > r || tr < l) return -1;
if(l <= tl && tr <= r) {
if(t[v].val >= x) return -1;
while(tl != tr) {
int mid = tl + (tr-tl)/2;
if(t[2*v].val <= x) {
v = 2*v;
tr = mid;
}else {
v = 2*v+1;
tl = mid+1;
}
}
return tl;
}
int mid = tl + (tr-tl)/2;
int rs = find(2*v, tl, mid, l, r, x);
if(rs != -1) return rs;
return find(2*v+1, mid+1, tr, l ,r, x);
}
int lower_bound(int l, int r, long long x) {
return find (1, 0,n-1,l, r, x);
}
il codice funziona per il caso d’esempio e per altri che ho creato io quindi non sono riuscito a trovare l’errore.