Submission #381826

#	Time	Username	Problem	Language	Result	Execution time	Memory
381826		Fireball0424	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	318 ms	188780 KiB

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 (stderr)

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

• Subtask 1: 100 / 100