Submission #898699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
898699	2024-01-05T03:29:51 Z	penguin133	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	248 ms	220812 KB

apple

#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(){
      | ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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