Submission #381826

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381826	2021-03-26T02:46:55 Z	Fireball0424	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	318 ms	188780 KB

apple

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

struct Seg{
	int l, r, mid, len, lz = 0, sum = 0;
	Seg *ch[2] = {nullptr, nullptr};
	Seg(int lc, int rc) : l(lc), r(rc), mid((lc + rc) >> 1), len(rc - lc + 1){}
	void pull(){
		sum = (ch[0] ? ch[0] -> sum : 0) + (ch[1] ? ch[1] -> sum : 0);
	}
	void push(){
		if(lz == 0) return;
		if(!ch[0]) ch[0] = new Seg(l, mid);
		if(!ch[1]) ch[1] = new Seg(mid + 1, r);
		for(int i : {0, 1}){
			ch[i] -> lz = 1;
			ch[i] -> sum = ch[i] -> len;
		}
		lz = 0;
	}
	void add(int lc, int rc){
		if(lc <= l && r <= rc){
			sum = len;
			lz = 1;
			return;
		}
		push();
		if(rc <= mid){
			if(!ch[0]) ch[0] = new Seg(l, mid);
			ch[0] -> add(lc, rc);
		}
		else if(lc > mid){
			if(!ch[1]) ch[1] = new Seg(mid + 1, r);
			ch[1] -> add(lc, rc);
		}
		else{
			if(!ch[0]) ch[0] = new Seg(l, mid);
			if(!ch[1]) ch[1] = new Seg(mid + 1, r);
			ch[0] -> add(lc, mid);
			ch[1] -> add(mid + 1, rc);
		}
		pull();
 	}
 	int query(int lc, int rc){
 		if(lc <= l && r <= rc) return sum;
 		push();
 		if(rc <= mid){
 			if(!ch[0]) return 0;
 			else if(ch[0] -> len == ch[0] -> sum) return (rc - lc + 1); 
 			return ch[0] -> query(lc, rc);
 		}
 		else if(lc > mid){
 			if(!ch[1]) return 0;
 			else if(ch[1] -> sum == ch[1] -> len) return (rc - lc + 1);
 			return ch[1] -> query(lc, rc);
 		}
 		else{
 			int sum = 0;
 			if(ch[0]){
 				if(ch[0] -> sum == ch[0] -> len) sum += mid - lc + 1;
 				else  sum += ch[0] -> query(lc, mid);
 			}
 			if(ch[1]){
 				if(ch[1] -> sum == ch[1] -> len) sum += rc - mid;
 				else  sum += ch[1] -> query(mid + 1, rc);
 			}
 			return sum;
 		}
 	}
};

void solve(){
	int n, last = 0;
	cin >> n;
	Seg seg(1, 1e9);
	while(n--){
		int t, x, y;
		cin >> t >> x >> y;
		if(t == 1){
			last = seg.query(x + last, y + last);
			cout << last << '\n';
		}
		else seg.add(x + last, y + last);
	}
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int t = 1;
	//cin >> t;
	while(t--) solve();
}

Compilation message

apple.cpp:88:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      |      ^

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	11 ms	4716 KB	Output is correct
5	Correct	13 ms	5612 KB	Output is correct
6	Correct	13 ms	5632 KB	Output is correct
7	Correct	13 ms	5612 KB	Output is correct
8	Correct	98 ms	43628 KB	Output is correct
9	Correct	195 ms	77676 KB	Output is correct
10	Correct	201 ms	84844 KB	Output is correct
11	Correct	218 ms	90220 KB	Output is correct
12	Correct	214 ms	92652 KB	Output is correct
13	Correct	205 ms	97004 KB	Output is correct
14	Correct	194 ms	99396 KB	Output is correct
15	Correct	316 ms	184940 KB	Output is correct
16	Correct	310 ms	185196 KB	Output is correct
17	Correct	201 ms	104684 KB	Output is correct
18	Correct	197 ms	104684 KB	Output is correct
19	Correct	318 ms	188652 KB	Output is correct
20	Correct	309 ms	188780 KB	Output is correct