제출 #381824

#제출 시각아이디문제언어결과실행 시간메모리
381824Fireball0424원숭이와 사과 나무 (IZhO12_apple)C++14
0 / 100
454 ms262148 KiB
#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();
}

컴파일 시 표준 에러 (stderr) 메시지

apple.cpp:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main(){
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...