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
#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);
		}
	}
}
# 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 -