#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,Q,niz[250005],res[250005];
int main(){
cin>>N;
for(int i=1;i<=N;i++)
cin>>niz[i];
cin>>Q;
while(Q--){
ll a,b,L,R;
cin>>a>>b>>L>>R;
L++;
niz[a]=b;
res[R]=1;
for(int i=R-1;i>=L;i--){
ll suma=0;
for(int j=i+1;j<=R;j++){
if(niz[j]<suma and niz[i]<suma)
res[i]=max(res[i],res[j]+2);
suma+=niz[j];
}
if(suma>niz[i])
res[i]=max(res[i],2ll);
}
ll r=max(res[L],1ll);
ll suma=niz[L];
for(int i=L+1;i<=R;i++){
if(suma>niz[i])
r=max(res[i]+1,r);
suma+=niz[i];
}
cout<<r<<endl;
}
return 0;
}
/*
4
6 2 3 2
1
3 2 1 3
5
1 2 3 4 5
3
1 1 1 2
1 1 1 5
1 1 0 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
446 ms |
3440 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
395 ms |
4252 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |