Submission #333038

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333038	2020-12-04T09:36:25 Z	nandonathaniel	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	163 ms	38252 KB

apple

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

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

void updatenode(int now,int L,int R){
	tree[now]=R-L+1;
	lazy[now]=1;
}

void pushdown(int now,int L,int R){
	if(lazy[now]==0)return;
	if(ki[now]==0){
		ki[now]=node;
		node++;
	}
	if(ka[now]==0){
		ka[now]=node;
		node++;
	}
	int mid=(L+R)/2;
	updatenode(ki[now],L,mid);
	updatenode(ka[now],mid+1,R);
	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){
		updatenode(now,L,R);
		return;
	}
	if(L>y || R<x)return;
	int mid=(L+R)/2;
	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;
	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	384 KB	Output is correct
4	Correct	7 ms	1260 KB	Output is correct
5	Correct	9 ms	1516 KB	Output is correct
6	Correct	9 ms	1388 KB	Output is correct
7	Correct	9 ms	1516 KB	Output is correct
8	Correct	56 ms	9324 KB	Output is correct
9	Correct	121 ms	16108 KB	Output is correct
10	Correct	125 ms	17516 KB	Output is correct
11	Correct	126 ms	18668 KB	Output is correct
12	Correct	127 ms	19052 KB	Output is correct
13	Correct	118 ms	20460 KB	Output is correct
14	Correct	116 ms	20332 KB	Output is correct
15	Correct	162 ms	37100 KB	Output is correct
16	Correct	161 ms	37356 KB	Output is correct
17	Correct	107 ms	20972 KB	Output is correct
18	Correct	106 ms	21100 KB	Output is correct
19	Correct	161 ms	38252 KB	Output is correct
20	Correct	163 ms	38252 KB	Output is correct