Submission #1129171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129171		FanOfWilliamLin	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	229 ms	68948 KiB

apple

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//- insert(x),erase(x)
//- find_by_order(k): return iterator to the k-th smallest element
//- order_of_key(x): the number of elements that are strictly smaller

#define ll long long
#define ld long double
#define ar array
#define vt vector
#define pb push_back
#define bit(i, x) ((x>>i)&1ULL)
#define pf push_front
#define all(v) v.begin(), v.end()
#define lla(v) v.rbegin(), v.rend()

/*mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r)(rng); 
}*/

const int mxN=1e9+1;

struct sparse_segment_tree {
	int n, q, timer=1;
	struct Node {
		int left=-1;
		int right=-1;
		int sum=0;
		int lz=0;
	};
	vt<Node> st;
	void init(int _n, int _q=0) {
		n=_n;
		q=_q;	
		if(q>0) {
			st.reserve(2*q*__lg(n));
		}
		st.pb(Node());
		st.pb(Node());
	}
	void app(int id, int len, int val) {
		if(val==1) {
			st[id].lz=val;
			st[id].sum=len*val;
		}
	}
	void psh(int id, int l, int r) {
		if(st[id].left==-1) {
			st[id].left=++timer;
			st.pb(Node());
		}
		if(st[id].right==-1) {
			st[id].right=++timer;
			st.pb(Node());
		}
		int mid=(l+r)/2;
		app(st[id].left, mid-l+1, st[id].lz);
		app(st[id].right, r-mid, st[id].lz);
		st[id].lz=0;
	}
	int range_sum(int id, int l, int r, int u, int v) {
		if(u>r||v<l) {
			return 0;
		}
		if(l>=u&&v>=r) {
			return st[id].sum;
		}
		int mid=(l+r)/2;
		psh(id, l, r);
		return range_sum(st[id].left, l, mid, u, v)+range_sum(st[id].right, mid+1, r, u, v);
	}
	void range_set(int id, int l, int r, int u, int v, int val) {
		if(u>r||v<l) {
			return;
		}
		if(l>=u&&v>=r) {
			app(id, r-l+1, val);
			return;
		}
		int mid=(l+r)/2;
		psh(id, l, r);
		range_set(st[id].left, l, mid, u, v, val);
		range_set(st[id].right, mid+1, r, u, v, val);
		st[id].sum=st[st[id].left].sum+st[st[id].right].sum;
	}
	int range_sum(int u, int v) {
		return range_sum(1, 1, n, u, v);
	}
	void range_set(int u, int v, int val) {
		range_set(1, 1, n, u, v, val);
	}
} st;

void solve() {
	int m;
	cin >> m;
	st.init(mxN, m);	
	int c=0;
	for(int i=0; i<m; ++i) {
		int op, x, y;
		cin >> op >> x >> y;
		if(op==1) {
			c=st.range_sum(x+c, y+c);
			cout << c << "\n";	
		}
		else {
			st.range_set(x+c, y+c, 1);
		}
	}
}
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	//freopen("template.inp", "r", stdin);
	//freopen("template.out", "w", stdout);	

	int TC=1;
	//cin >> TC;
	while(TC--) {
		solve();
	}
}
//try again :)

• Subtask 1: 100 / 100