durante la prima gara delle olimpiadi di informatica di quest’anno era capitato questo problema, e nonostante non conoscessi ancora i segment tree ho voluto provare a risolverlo per prendere i punti delle prime tre subtask(60/100) tuttavia ancora adesso non riesco a capire cosa ci sia di sbagliato in questo codice, e prima di scrivere la soluzione “veloce” vorrei capire cosa sbaglia il programma che ho scritto.
praticamente uso la definizione dei numeri triangolari per calcolare il numero di possibili risultato solo se il range di valori non rientra in uno dei casi speciali che non rispetta questa formula, questo è il codice:
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
// input data
int N, Q, K, type;
vector<int> V;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
in >> N >> Q >> K;
V.resize(N+1);
for (int i=1; i<=N; i++){
in >> V[i];
V[i]=max(V[i],K);
}
for (int i=0; i<Q; i++) {
in >> type;
if (type == 1) {
// building update
int a, b;
in >> a >> b;
V[a]=max(b,K);
}
if (type == 2) {
// redevelopment planning
int l, r, s;
in >> l >> r >> s;
for(int j=l;j<=r;j++)s-=V[j];
if(s<0) out <<0<< endl;
else if(s==0)out<<1<<endl;
else if(l==r)out<<1<<endl;
else if((r-l)==1)out<<s+1;
else if(s==1)out<<r-l+1<<endl;
else{
int n=r-l+s-1;
out<<(long long)(n*(n+1)/2)%mod<<endl;
}
}
}
return 0;
}