Submission #898696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
898696	2024-01-05T03:27:34 Z	penguin133	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	315 ms	262144 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){
		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:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main(){
      | ^~~~

Subtask #1

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	12 ms	10328 KB	Output is correct
5	Correct	16 ms	12380 KB	Output is correct
6	Correct	16 ms	11968 KB	Output is correct
7	Correct	16 ms	12380 KB	Output is correct
8	Correct	132 ms	92892 KB	Output is correct
9	Correct	288 ms	158948 KB	Output is correct
10	Correct	293 ms	177724 KB	Output is correct
11	Correct	315 ms	192340 KB	Output is correct
12	Correct	314 ms	198532 KB	Output is correct
13	Correct	291 ms	242776 KB	Output is correct
14	Correct	281 ms	245840 KB	Output is correct
15	Runtime error	279 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-