Submission #381823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381823	2021-03-26T02:32:15 Z	Fireball0424	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	422 ms	262148 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) return (ch[0] ? ch[0] -> query(lc, rc) : 0);
 		else if(lc > mid) return (ch[1] ? ch[1] -> query(lc, rc) : 0);
 		return (ch[0] ? ch[0] -> query(lc, mid) : 0) + (ch[1] ? ch[1] -> query(mid + 1, rc) : 0);
 	}
};

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);
	//freopen("f.in", "r", stdin);
	//freopen("f.out", "w", stdout);
	int t = 1;
	//cin >> t;
	while(t--) solve();
}

Compilation message

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	380 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	16 ms	8044 KB	Output is correct
5	Correct	20 ms	9708 KB	Output is correct
6	Correct	19 ms	9452 KB	Output is correct
7	Correct	20 ms	9708 KB	Output is correct
8	Correct	162 ms	73452 KB	Output is correct
9	Correct	328 ms	127340 KB	Output is correct
10	Correct	345 ms	140780 KB	Output is correct
11	Correct	364 ms	151148 KB	Output is correct
12	Correct	365 ms	156012 KB	Output is correct
13	Correct	327 ms	181484 KB	Output is correct
14	Correct	332 ms	183276 KB	Output is correct
15	Runtime error	422 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-