Submission #381824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381824	2021-03-26T02:41:15 Z	Fireball0424	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	454 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){
 			if(!ch[0]) return 0;
 			return ch[0] -> query(lc, rc);
 		}
 		else if(lc > mid){
 			if(!ch[1]) return 0;
 			return ch[1] -> query(lc, rc);
 		}
 		else{
 			int sum = 0;
 			if(ch[0]) sum += ch[0] -> query(lc, mid);
 			if(ch[1]) 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:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main(){
      |      ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	17 ms	8044 KB	Output is correct
5	Correct	20 ms	9580 KB	Output is correct
6	Correct	19 ms	9324 KB	Output is correct
7	Correct	20 ms	9580 KB	Output is correct
8	Correct	168 ms	72556 KB	Output is correct
9	Correct	349 ms	125676 KB	Output is correct
10	Correct	358 ms	138988 KB	Output is correct
11	Correct	408 ms	149484 KB	Output is correct
12	Correct	421 ms	154240 KB	Output is correct
13	Correct	326 ms	179436 KB	Output is correct
14	Correct	349 ms	181452 KB	Output is correct
15	Runtime error	454 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-