Submission #909673

#	Time	Username	Problem	Language	Result	Execution time	Memory
909673		dsyz	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	421 ms	262144 KiB

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