Submission #1065583

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

apple

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;
using ll = long long;
const ll MAX_N = (1e9 + 5);
const ll MAX_CONST = (5e6);

template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec){for (auto itr : vec){os << itr << " ";} return os;}
auto start_time = chrono::high_resolution_clock().now();
auto end_time = chrono::high_resolution_clock().now();

ll m;
ll c;
ll last_node;
ll seg;
vector<ll> val;
vector<ll> left_node;
vector<ll> right_node;

vector<ll> lazy;

void st_time(){
	start_time = chrono::high_resolution_clock().now();
}

void pr_time(){
	end_time = chrono::high_resolution_clock().now();
	cout << "time is " << chrono::duration_cast<chrono::microseconds>(end_time-start_time).count() << endl;
}


inline void extend(ll ind, ll l, ll r){
	if(l == r){return;}

	if(left_node[ind] == -1){
		left_node[ind] = ++last_node;
	}

	if(right_node[ind] == -1){
		right_node[ind] = ++last_node;
	}
}

inline void pushdownwards(ll ind, ll l, ll r){
	extend(ind, l, r);
	if(lazy[ind] == 0){return;}

	val[ind] = (r-l+1) * 1;

	if(l != r){
		lazy[left_node[ind]] = 1;
		lazy[right_node[ind]] = 1;
	}

	lazy[ind] = 0;
}

/*
int query(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr)
		return segtree[node].sum;
	else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}

		if (l > mid) return query(segtree[node].r, l, r);
		else if (r <= mid) return query(segtree[node].l, l, r);
		else
			return query(segtree[node].l, l, mid) +
			       query(segtree[node].r, mid + 1, r);
	}
}
*/

inline ll get_val(ll ind, ll tl, ll tr, ll l, ll r){
	pushdownwards(ind, l, r);

	if(max<ll>(l,tl) > min<ll>(r,tr)){return 0;}
	if(tl <= l && r <= tr){return val[ind];}

	ll m = (r-l)/2+l;
	extend(ind, l, r);

	if(m < tl){
		return get_val(right_node[ind], tl, tr, m+1, r);
	}else if(tr <= m){
		return get_val(left_node[ind], tl, tr, l, m);
	}else{
		return get_val(left_node[ind], tl, m, l, m)+get_val(right_node[ind], m+1, tr, m+1, r);
	}

}

/*
void update(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		push_lazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}

		if (l > mid) update(segtree[node].r, l, r);
		else if (r <= mid) update(segtree[node].l, l, r);
		else {
			update(segtree[node].l, l, mid);
			update(segtree[node].r, mid + 1, r);
		}

		push_lazy(segtree[node].l);
		push_lazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}
*/

inline void upd(ll ind, ll tl, ll tr, ll l, ll r){
	pushdownwards(ind, l, r);

	if(max<ll>(l,tl) > min<ll>(r,tr)){return;}
	
	if(tl <= l && r <= tr){
		lazy[ind] = 1; pushdownwards(ind, l, r);
	}else{
		ll m = (r-l)/2+l;
		extend(ind,l,r);

		if(m < tl){
			upd(right_node[ind], tl, tr, m+1, r);	
		}else if(tr <= m){
			upd(left_node[ind], tl, tr, l, m);
		}else{
			upd(left_node[ind], tl, m, l, m);
			upd(right_node[ind], m+1, tr, m+1, r);
		}

		pushdownwards(left_node[ind], l, m);
		pushdownwards(right_node[ind], m+1, r);
		val[ind] = val[left_node[ind]] + val[right_node[ind]];
	}

	pushdownwards(ind, l, r);
}


void dfs(ll ind, string str){
	cout << str << " " << val[ind] << endl;

	if(left_node[ind] != -1){
		dfs(left_node[ind], str+"L");
	}
	if(right_node[ind] != -1){
		dfs(right_node[ind], str+"R");
	}
}

void solve(){

	cin >> m;
	c = 0;
	last_node = 0;
	val.assign(MAX_CONST,0);
	left_node.assign(MAX_CONST,-1);
	right_node.assign(MAX_CONST,-1);

	lazy.assign(MAX_CONST, 0);

	seg = ++last_node;


	for(ll i=0; i<m; i++){
		ll opr,l,r;
		cin >> opr >> l >> r;

		if(opr == 1){
			ll res = get_val(1, l+c, r+c, 0, MAX_N);
			c = res;

			cout << res << "\n";
		}else{
			upd(1, l+c, r+c, 0, MAX_N);
		}
	}
}
int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	solve();
}

• Subtask 1: 0 / 100