Submission #486586

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
486586	2021-11-12T05:05:52 Z	Gurban	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	255 ms	105428 KB

apple

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;

struct Node{
	int val,laz,l,r,lfc,rgc;
};

const int maxn=1e5+5;
int M,sz,C;
Node T[60*maxn];

void CL(int idx){
	sz++;
	T[sz].l = T[idx].l;
	T[sz].r = (T[idx].l + T[idx].r) / 2;
	
	T[idx].lfc = sz;
}
void CR(int idx){
	sz++;
	int md = (T[idx].l + T[idx].r) / 2;
	T[sz].l = md + 1;
	T[sz].r = T[idx].r;
	
	T[idx].rgc = sz;
}

void prop(int nd){
	if(T[nd].lfc == 0) CL(nd);
	if(T[nd].rgc == 0) CR(nd);
	
	if(T[nd].laz == 0) return;
	int lftC = T[nd].lfc;
	int rgtC = T[nd].rgc;
	T[lftC].val = T[lftC].r - T[lftC].l + 1;
	T[lftC].laz = 1;
	T[rgtC].val = T[rgtC].r - T[rgtC].l + 1;
	T[rgtC].laz = 1;
	T[nd].laz = 0;
}

void upd(int a,int b,int nd){
	if(T[nd].r < a or T[nd].l > b) return;
	if(T[nd].l >= a and T[nd].r <= b){
		T[nd].val = T[nd].r - T[nd].l + 1;
		T[nd].laz = 1;
		return;
	}
	prop(nd);
	upd(a,b,T[nd].lfc);
	upd(a,b,T[nd].rgc);
	T[nd].val = T[T[nd].lfc].val + T[T[nd].rgc].val;
}

int tap(int a,int b,int nd){
	if(T[nd].r < a or T[nd].l > b) return 0;
	if(T[nd].l >= a and T[nd].r <= b) return T[nd].val;
	prop(nd);
	return tap(a,b,T[nd].lfc) + tap(a,b,T[nd].rgc);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	sz = 1;
	T[1].l = 1;
	T[1].r = 1e9;
	
	cin >> M;
	while(M--){
		int tp,x,y; cin >> tp >> x >> y;
		if(tp == 1){
			int val = tap(x + C,y + C,1);
			cout<<val<<'\n';
			C = val;
		}
		else upd(x + C,y + C,1);
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	312 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	10 ms	2656 KB	Output is correct
5	Correct	12 ms	3276 KB	Output is correct
6	Correct	13 ms	3152 KB	Output is correct
7	Correct	13 ms	3276 KB	Output is correct
8	Correct	91 ms	22916 KB	Output is correct
9	Correct	185 ms	39876 KB	Output is correct
10	Correct	186 ms	43908 KB	Output is correct
11	Correct	191 ms	47000 KB	Output is correct
12	Correct	192 ms	48452 KB	Output is correct
13	Correct	171 ms	56332 KB	Output is correct
14	Correct	180 ms	56972 KB	Output is correct
15	Correct	248 ms	102340 KB	Output is correct
16	Correct	254 ms	103072 KB	Output is correct
17	Correct	174 ms	58828 KB	Output is correct
18	Correct	175 ms	58808 KB	Output is correct
19	Correct	254 ms	105280 KB	Output is correct
20	Correct	255 ms	105428 KB	Output is correct