Submission #909673

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

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node{
	ll s,e,m,val,lazy;
	node *l = nullptr, *r = nullptr;
	node(ll S,ll E){
		s = S;
		e = E;
		m = (s + e) / 2;
		val = 0;
		lazy = -1;
	}
	void create(){
		if(l == nullptr && s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propagate(){
		create();
		if(lazy == -1) return;
		val = lazy * (e - s + 1);
		if(s != e){
			l->lazy = lazy;
			r->lazy = lazy;
		}
		lazy = -1;
	}
	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	0 ms	348 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	16 ms	10328 KB	Output is correct
5	Correct	19 ms	12456 KB	Output is correct
6	Correct	17 ms	12124 KB	Output is correct
7	Correct	17 ms	12632 KB	Output is correct
8	Correct	172 ms	93196 KB	Output is correct
9	Correct	393 ms	159836 KB	Output is correct
10	Correct	411 ms	178260 KB	Output is correct
11	Correct	421 ms	192944 KB	Output is correct
12	Correct	420 ms	199188 KB	Output is correct
13	Correct	345 ms	243532 KB	Output is correct
14	Correct	347 ms	246612 KB	Output is correct
15	Runtime error	331 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-