Submission #333032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333032	2020-12-04T09:30:28 Z	nandonathaniel	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	265 ms	95980 KB

apple

#include<bits/stdc++.h>
using namespace std;

int tree[3000005],lazy[3000005],ki[3000005],ka[3000005],node=2;

void pushdown(int now,int L,int R){
	int mid=(L+R)/2;
	if(ki[now]==0){
		ki[now]=node;
		node++;
	}
	if(ka[now]==0){
		ka[now]=node;
		node++;
	}
	tree[ki[now]]=mid-L+1;
	lazy[ki[now]]=1;
	tree[ka[now]]=R-mid;
	lazy[ka[now]]=1;
	lazy[now]=0;
}

void update(int now,int L,int R,int x,int y){
    //if(tree[now]==R-L+1)return;
	if(L>=x && R<=y){
		tree[now]=R-L+1;
		lazy[now]=1;
		return;
	}
	if(L>y || R<x)return;
	int mid=(L+R)/2;
	if(lazy[now])pushdown(now,L,R);
	if(ki[now]==0){
		ki[now]=node;
		node++;
	}
	if(ka[now]==0){
		ka[now]=node;
		node++;
	}
	update(ki[now],L,mid,x,y);
	update(ka[now],mid+1,R,x,y);
	tree[now]=tree[ki[now]]+tree[ka[now]];
}

int query(int now,int L,int R,int x,int y){
	if(L>=x && R<=y){
		return tree[now];
	}
	if(L>y || R<x || now==0)return 0;
	if(lazy[now])pushdown(now,L,R);
	int mid=(L+R)/2;
	return query(ki[now],L,mid,x,y)+query(ka[now],mid+1,R,x,y);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int q,op,x,y,c=0;
	cin >> q;
	while(q--){
		cin >> op >> x >> y;
		x+=c;
		y+=c;
		if(op==1){
			c=query(1,1,1e9,x,y);
			cout << c << '\n';
		}
		else update(1,1,1e9,x,y);
	}
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	11 ms	1900 KB	Output is correct
5	Correct	13 ms	2284 KB	Output is correct
6	Correct	13 ms	2156 KB	Output is correct
7	Correct	14 ms	2284 KB	Output is correct
8	Correct	108 ms	15084 KB	Output is correct
9	Correct	235 ms	25708 KB	Output is correct
10	Correct	242 ms	28652 KB	Output is correct
11	Correct	242 ms	30572 KB	Output is correct
12	Correct	243 ms	31468 KB	Output is correct
13	Correct	210 ms	36716 KB	Output is correct
14	Correct	207 ms	36972 KB	Output is correct
15	Runtime error	265 ms	95980 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-