#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 25e4;
const int INF = 1e9+1;
const int SQ = 500;
int N, Q, A[MAXN+10];
struct SEG
{
ll tree[MAXN*4+10];
void update(int node, int tl, int tr, int x)
{
if(tl==tr)
{
tree[node]=A[x];
return;
}
int mid=tl+tr>>1;
if(x<=mid) update(node*2, tl, mid, x);
else update(node*2+1, mid+1, tr, x);
tree[node]=tree[node*2]+tree[node*2+1];
}
ll query(int node, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
}
int queryr(int node, int tl, int tr, int l, int r, int &y)
{
//printf("!%d %d %d %d %d\n", tl, tr, l, r, y);
if(r<tl || tr<l) return -1;
if(l<=tl && tr<=r && tree[node]<=y)
{
y-=tree[node];
return -1;
}
if(tl==tr) return tl;
int mid=tl+tr>>1, ret;
ret=queryr(node*2, tl, mid, l, r, y);
if(ret!=-1) return ret;
ret=queryr(node*2+1, mid+1, tr, l, r, y);
return ret;
}
int queryr(int l, int r, int y)
{
int t=queryr(1, 1, N, l, r, y);
if(t==-1) return INF;
return t+1;
}
}seg;
struct SEG2
{
ll tree[MAXN*4+10], lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
if(!lazy[node]) return;
tree[node]+=lazy[node];
if(tl!=tr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void update(int node, int tl, int tr, int l, int r, ll k)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
int query(int node, int tl, int tr, int l, int r, ll y)
{
busy(node, tl, tr);
if(r<tl || tr<l) return -1;
if(l<=tl && tr<=r && tree[node]<=y) return -1;
if(tl==tr) return tl;
int mid=tl+tr>>1, ret;
ret=query(node*2, tl, mid, l, r, y);
if(ret!=-1) return ret;
ret=query(node*2+1, mid+1, tr, l, r, y);
return ret;
}
int query(int l, int r, int y)
{
int t=query(1, 1, N, l, r, y);
return t;
}
}seg2;
int P[MAXN+10], P2[MAXN+10], Q2[MAXN+10];
int f(int now, int b)
{
int t=1;
while(now/SQ<b/SQ)
{
if(P2[now]!=-1)
{
t+=Q2[now];
now=P2[now];
}
int tt=seg.queryr(now+1, b, A[now]);
ll s=seg.query(1, 1, N, 1, now);
now=seg2.query(tt, b, s);
t++;
if(now==-1) break;
}
while(now!=-1 && now<b)
{
//printf("!%d %d\n", now, P[now]);
if(P[now]!=-1 && P[now]<=b)
{
now=P[now];
t+=2;
}
else
{
int tt=seg.queryr(now+1, b, A[now]);
//printf("??%d\n", tt);
if(tt>b+1) t--;
else t++;
break;
}
}
return t;
}
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
for(int i=1; i<=N; i++)
{
seg.update(1, 1, N, i);
seg2.update(1, 1, N, i+1, N, A[i]);
seg2.update(1, 1, N, i, i, -A[i]);
}
for(int i=0; i<=N/SQ; i++)
{
int l=max(1, i*SQ), r=min(N, i*SQ+SQ-1);
for(int j=r; j>=l; j--)
{
int t=seg.queryr(j+1, r, A[j]);
ll s=seg.query(1, 1, N, 1, j);
P[j]=seg2.query(t, r, s);
if(P[j]==-1) P2[j]=-1, Q2[j]=0;
else P2[j]=P[P2[j]], Q2[j]=Q2[P[j]]+2;
}
}
//for(int i=1; i<=N; i++) printf("%d ", P[i]); printf("\n");
//for(int i=1; i<=N; i++) printf("%d ", Q2[i]); printf("\n");
scanf("%d", &Q);
while(Q--)
{
int x, y, a, b;
scanf("%d%d%d%d", &x, &y, &a, &b);
seg2.update(1, 1, N, x+1, N, -A[x]+y);
seg2.update(1, 1, N, x, x, -y+A[x]);
A[x]=y; a++;
seg.update(1, 1, N, x);
int l=max(1, x/SQ*SQ), r=min(N, x/SQ*SQ+SQ-1);
for(int j=r; j>=l; j--)
{
int t=seg.queryr(j+1, r, A[j]);
ll s=seg.query(1, 1, N, 1, j);
P[j]=seg2.query(t, r, s);
if(P[j]==-1) P2[j]=-1, Q2[j]=0;
else P2[j]=P[P2[j]], Q2[j]=Q2[P[j]]+2;
}
int ans=max(1, f(a, b));
int t=seg2.query(a, b, seg.query(1, 1, N, 1, a-1));
if(t!=-1) ans=max(ans, 1+f(t, b));
printf("%d\n", ans);
}
}
Compilation message
mizuyokan2.cpp: In member function 'void SEG::update(int, int, int, int)':
mizuyokan2.cpp:24:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int mid=tl+tr>>1;
| ~~^~~
mizuyokan2.cpp: In member function 'll SEG::query(int, int, int, int, int)':
mizuyokan2.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid=tl+tr>>1;
| ~~^~~
mizuyokan2.cpp: In member function 'int SEG::queryr(int, int, int, int, int, int&)':
mizuyokan2.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid=tl+tr>>1, ret;
| ~~^~~
mizuyokan2.cpp: In member function 'void SEG2::update(int, int, int, int, int, ll)':
mizuyokan2.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid=tl+tr>>1;
| ~~^~~
mizuyokan2.cpp: In member function 'int SEG2::query(int, int, int, int, int, ll)':
mizuyokan2.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int mid=tl+tr>>1, ret;
| ~~^~~
mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
mizuyokan2.cpp:149:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | for(int i=1; i<=N; i++) scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
mizuyokan2.cpp:173:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
mizuyokan2.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
177 | scanf("%d%d%d%d", &x, &y, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Execution timed out |
4022 ms |
16520 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Execution timed out |
4065 ms |
17236 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
