Submission #333031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333031	2020-12-04T09:30:04 Z	nandonathaniel	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	175 ms	40608 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

100.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	8 ms	1388 KB	Output is correct
5	Correct	9 ms	1644 KB	Output is correct
6	Correct	12 ms	1644 KB	Output is correct
7	Correct	10 ms	1644 KB	Output is correct
8	Correct	58 ms	10220 KB	Output is correct
9	Correct	123 ms	17772 KB	Output is correct
10	Correct	132 ms	19420 KB	Output is correct
11	Correct	126 ms	20348 KB	Output is correct
12	Correct	131 ms	20844 KB	Output is correct
13	Correct	119 ms	22636 KB	Output is correct
14	Correct	120 ms	22508 KB	Output is correct
15	Correct	159 ms	39276 KB	Output is correct
16	Correct	161 ms	39532 KB	Output is correct
17	Correct	108 ms	23020 KB	Output is correct
18	Correct	113 ms	23148 KB	Output is correct
19	Correct	165 ms	40412 KB	Output is correct
20	Correct	175 ms	40608 KB	Output is correct