Submission #909675

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
909675	2024-01-17T10:32:30 Z	dsyz	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	523 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (1000005)
struct node{
	ll s,e,m,val;
	bool lazy;
	node *l = nullptr, *r = nullptr;
	node(ll S,ll E){
		s = S;
		e = E;
		m = (s + e) / 2;
		val = 0;
		lazy = 0;
	}
	void create(){
		if(l == nullptr && s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propagate(){
		create();
		if(lazy == 0) return;
		val = lazy * (e - s + 1);
		if(s != e){
			l->lazy = lazy;
			r->lazy = lazy;
		}
		lazy = 0;
	}
	void update(ll S,ll E,ll v){
		if(s == S && e == E) lazy = v;
		else{
			create();
			if(E <= m) l->update(S,E,v);
			else if(S > m) r->update(S,E,v);
			else l->update(S,m,v),r->update(m + 1,E,v);
			l->propagate(),r->propagate();
			val = l->val + r->val;
		}
	}
	ll query(ll S,ll E){
		create();
		propagate();
		if(s == S && e == E) return val;
		else if(S > m) return r->query(S,E);
		else if(E <= m) return l->query(S,E);
		else return l->query(S,m) + r-> query(m + 1,E);
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll M;
	cin>>M;
	root = new node(0,1e9 + 5);
	ll C = 0;
	while(M--){
		ll D,X,Y;
		cin>>D>>X>>Y;
		X += C, Y += C;
		if(D == 1){ //query
			C = root -> query(X,Y);
			cout<<C<<'\n';
		}else if(D == 2){ //update
			root -> update(X,Y,1);
		}
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	13 ms	7772 KB	Output is correct
5	Correct	22 ms	9372 KB	Output is correct
6	Correct	23 ms	9096 KB	Output is correct
7	Correct	24 ms	9808 KB	Output is correct
8	Correct	171 ms	70036 KB	Output is correct
9	Correct	371 ms	119680 KB	Output is correct
10	Correct	388 ms	133780 KB	Output is correct
11	Correct	438 ms	144588 KB	Output is correct
12	Correct	435 ms	149316 KB	Output is correct
13	Correct	372 ms	182752 KB	Output is correct
14	Correct	356 ms	184972 KB	Output is correct
15	Runtime error	523 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-