#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF1 = 1e9 + 100;
int n;
int a[250250];
int go[250250], sp[250250][20];
ll S[250250];
void init(int n){
for (int i=1;i<=n;i++) S[i] = S[i-1] + a[i];
go[n+1] = n+1;
for (int i=1;i<=n;i++){
go[i] = n+1;
for (int j=i+2;j<=min(i+50, n);j++) if (S[j-1] - S[i] > max(a[i], a[j])){
go[i] = j;
break;
}
if (i+50 < n) assert(go[i] <= n);
}
for (int i=n;i;i--) go[i] = min(go[i], go[i+1]);
for (int i=1;i<=n+1;i++) sp[i][0] = go[i];
for (int j=1;j<20;j++){
for (int i=1;i<=n+1;i++) sp[i][j] = sp[sp[i][j-1]][j-1];
}
}
int solve(int l, int r){
if (r-l+1 < 3) return -INF1;
int cnt = 0;
for (int x=l,j=19;j>=0;j--) if (sp[x][j] <= r){
x = sp[x][j];
cnt |= 1<<j;
}
return cnt * 2 + 1;
}
int query(int l, int r){
int ret = 1;
if (l==r) return ret;
if (S[r-1]-S[l-1] > a[r]) ret = 2;
if (S[r]-S[l] > a[l]) ret = 2;
int nl = r+1, nr = l-1;
for (int i=l+1;i<=min(l+30, r);i++) if (S[i-1]-S[l-1] > a[i]) {nl = i; break;}
for (int i=r-1;i>=max(l, r-30);i--) if (S[r]-S[i] > a[i]) {nr = i; break;}
if (nl <= nr) ret = 3;
return max({ret, solve(l, r), solve(nl, r) + 1, solve(l, nr) + 1, solve(nl, nr) + 2});
}
void update(int x, int y){
a[x] = y;
init(n);
}
int main(){
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%d", a+i);
init(n);
int q;
scanf("%d", &q);
while(q--){
int x, y, l, r;
scanf("%d %d %d %d", &x, &y, &l, &r);
if (a[x]!=y) update(x, y);
l++;
printf("%d\n", query(l, r));
}
}
Compilation message
mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
mizuyokan2.cpp:68:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | for (int i=1;i<=n;i++) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
mizuyokan2.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
mizuyokan2.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d %d %d %d", &x, &y, &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Runtime error |
6 ms |
8796 KB |
Execution killed with signal 6 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Runtime error |
6 ms |
8796 KB |
Execution killed with signal 6 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Runtime error |
6 ms |
8796 KB |
Execution killed with signal 6 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
57 ms |
19696 KB |
Output is correct |
| 3 |
Runtime error |
25 ms |
10588 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Execution timed out |
4056 ms |
23644 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Runtime error |
6 ms |
8796 KB |
Execution killed with signal 6 |
| 12 |
Halted |
0 ms |
0 KB |
- |
