Submission #909684

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
909684	2024-01-17T10:39:31 Z	dsyz	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	450 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){
		propagate();
		if(s == S && e == E) lazy = v;
		else{
			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){
		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 D, X, Y, C = 0;
	while(M--){
		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	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	16 ms	7772 KB	Output is correct
5	Correct	16 ms	9432 KB	Output is correct
6	Correct	19 ms	9052 KB	Output is correct
7	Correct	16 ms	9264 KB	Output is correct
8	Correct	151 ms	69224 KB	Output is correct
9	Correct	338 ms	118612 KB	Output is correct
10	Correct	348 ms	132660 KB	Output is correct
11	Correct	372 ms	143588 KB	Output is correct
12	Correct	346 ms	148416 KB	Output is correct
13	Correct	296 ms	181304 KB	Output is correct
14	Correct	329 ms	183664 KB	Output is correct
15	Runtime error	450 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-