Submission #909716

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
909716	2024-01-17T11:04:43 Z	dsyz	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	246 ms	164720 KB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (1000005)
struct node{
	ll s,e,m,v;
	bool lazy;
	node *l = nullptr, *r = nullptr;
	node(ll S,ll E){
		s = S;
		e = E;
		m = (s + e) / 2;
		v = 0;
		lazy = 0;
	}
	void create(){
		if(l == nullptr && s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propo(){
		create();
		if(lazy == 0) return;
		v = lazy * (e - s + 1);
		if(s != e){
			l->lazy = lazy;
			r->lazy = lazy;
		}
		lazy = 0;
	}
	void update(ll x,ll y,ll nval){
		if(v == e - s + 1) return;
		propo();
		if(s == x && e == y){
			lazy = nval;
			return;
		}else{
			if(x > m) r -> update(x,y,nval);
			else if(y <= m) l -> update(x,y,nval);
			else l -> update(x,m,nval), r -> update(m + 1,y,nval);
			l->propo(), r->propo();
			v = l->v + r->v;
		}
	}
	ll query(ll x,ll y){
		propo();
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r->query(x,y);
			else if(y <= m) return l->query(x,y);
			else return l->query(x,m) + r-> query(m + 1,y);
		}
	}
} *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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	4188 KB	Output is correct
5	Correct	9 ms	4956 KB	Output is correct
6	Correct	9 ms	4700 KB	Output is correct
7	Correct	9 ms	4956 KB	Output is correct
8	Correct	68 ms	37572 KB	Output is correct
9	Correct	138 ms	65312 KB	Output is correct
10	Correct	147 ms	71572 KB	Output is correct
11	Correct	153 ms	76820 KB	Output is correct
12	Correct	168 ms	78684 KB	Output is correct
13	Correct	166 ms	86868 KB	Output is correct
14	Correct	145 ms	86556 KB	Output is correct
15	Correct	239 ms	159848 KB	Output is correct
16	Correct	238 ms	161108 KB	Output is correct
17	Correct	150 ms	89212 KB	Output is correct
18	Correct	158 ms	89568 KB	Output is correct
19	Correct	246 ms	164628 KB	Output is correct
20	Correct	240 ms	164720 KB	Output is correct