Submission #736281

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736281	2023-05-05T11:55:43 Z	Dan4Life	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	320 ms	124732 KB

apple

#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)3e5+10;
int mx=(int)1e9, segTree[mxN*40], lazy[mxN*40];
int L[mxN*40], R[mxN*40], IND = 1, q,c;

void prop(int p, int l, int r){
	if(!p or l==r or lazy[p]==-1) return;
	int mid = (l+r)/2;
	if(!L[p]) L[p]=++IND;
	if(!R[p]) R[p]=++IND;
	lazy[L[p]]=lazy[R[p]]=lazy[p]; lazy[p]=-1;
	segTree[L[p]] = (mid-l+1)*lazy[L[p]];
	segTree[R[p]] = (r-mid)*lazy[R[p]];
}

void upd(int i, int j, int v, int p=1, int l=1, int r=mx){
	if(i>r or j<l or i>j or !p) return; prop(p,l,r);
	if(i<=l and r<=j){ segTree[p] = v*(r-l+1); lazy[p] = v; return; }
	int mid = (l+r)/2;
	if(i<=mid){
		if(!L[p]) L[p]=++IND;
		upd(i,j,v,L[p],l,mid);
	}
	if(j>mid){
		if(!R[p]) R[p]=++IND;
		upd(i,j,v,R[p],mid+1,r);
	}
	segTree[p]=segTree[L[p]]+segTree[R[p]];
}

int query(int i, int j, int p=1, int l=1, int r=mx){
	if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
	if(i<=l and r<=j) return segTree[p];
	int mid = (l+r)/2;
	return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> q; memset(lazy,-1,sizeof(lazy));
    while(q--){
        int t, x, y; cin >> t >> x >> y; x+=c, y+=c;
        if(t==1) c = query(x,y), cout << c << "\n";
        else upd(x,y,1);
    }
}

Compilation message

apple.cpp: In function 'void upd(int, int, int, int, int, int)':
apple.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |  if(i>r or j<l or i>j or !p) return; prop(p,l,r);
      |  ^~
apple.cpp:18:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |  if(i>r or j<l or i>j or !p) return; prop(p,l,r);
      |                                      ^~~~
apple.cpp: In function 'int query(int, int, int, int, int)':
apple.cpp:33:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |  if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
      |  ^~
apple.cpp:33:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |  if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
      |                                        ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	47220 KB	Output is correct
2	Correct	24 ms	47252 KB	Output is correct
3	Correct	20 ms	47200 KB	Output is correct
4	Correct	31 ms	48972 KB	Output is correct
5	Correct	31 ms	49356 KB	Output is correct
6	Correct	33 ms	49300 KB	Output is correct
7	Correct	33 ms	49360 KB	Output is correct
8	Correct	112 ms	63496 KB	Output is correct
9	Correct	248 ms	75472 KB	Output is correct
10	Correct	253 ms	78384 KB	Output is correct
11	Correct	248 ms	80844 KB	Output is correct
12	Correct	234 ms	81868 KB	Output is correct
13	Correct	226 ms	88928 KB	Output is correct
14	Correct	208 ms	89332 KB	Output is correct
15	Correct	320 ms	122316 KB	Output is correct
16	Correct	311 ms	122860 KB	Output is correct
17	Correct	235 ms	90816 KB	Output is correct
18	Correct	199 ms	90748 KB	Output is correct
19	Correct	302 ms	124532 KB	Output is correct
20	Correct	296 ms	124732 KB	Output is correct