답안 #898699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898699 2024-01-05T03:29:51 Z penguin133 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
248 ms 220812 KB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int s, e, m, val, lz;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		val = lz = 0;
		l = r = nullptr;
	}
	
	void mc(){
		if(l != nullptr || s == e)return;
		l = new node(s, m);
		r = new node(m+1, e);
	}
	
	void prop(){
		if(lz){
			val = lz * (e - s + 1);
			if(s != e)mc(), l->lz = lz, r->lz = lz;
			lz = 0;
		}
	}
	
	void upd(int a, int b, int c){
		if(val == e - s + 1)return;
		prop();
		if(a == s && b == e)lz = c;
		else{
			mc();
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->prop(), r->prop();
			val = l->val + r->val;
		}
	}
	
	int qry(int a, int b){
		prop();
		if(l == nullptr)return val;
		if(a == s && b == e)return val;
		else if(b <= m)return l->qry(a, b);
		else if(a > m)return r->qry(a, b);
		else return l->qry(a, m) + r->qry(m+1, b);
	}
}*root = new node(0, 1e9 + 5);

void solve(){
	int q; cin >> q;
	int c = 0;
	while(q--){
		int d, x, y; cin >> d >> x >> y;
		if(d == 1){
			c = root->qry(x + c, y + c);
			cout << c << '\n';
		}
		else{
			root->upd(x+c, y+c, 1);
		}
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

apple.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 5464 KB Output is correct
5 Correct 10 ms 6748 KB Output is correct
6 Correct 9 ms 6236 KB Output is correct
7 Correct 10 ms 6608 KB Output is correct
8 Correct 72 ms 49960 KB Output is correct
9 Correct 149 ms 86880 KB Output is correct
10 Correct 144 ms 95312 KB Output is correct
11 Correct 161 ms 101968 KB Output is correct
12 Correct 149 ms 104636 KB Output is correct
13 Correct 172 ms 115540 KB Output is correct
14 Correct 159 ms 115236 KB Output is correct
15 Correct 241 ms 213588 KB Output is correct
16 Correct 248 ms 215652 KB Output is correct
17 Correct 151 ms 119840 KB Output is correct
18 Correct 151 ms 120288 KB Output is correct
19 Correct 245 ms 220812 KB Output is correct
20 Correct 236 ms 219532 KB Output is correct