Submission #1064744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064744		MrNanama	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	88 ms	157016 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;}

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

vector<ll> lazy;

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

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

ll get_val(ll ind, ll tl, ll tr, ll l, ll r){
	extend(ind, l, 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;
	return get_val(left_node[ind], tl, tr, l, m)+get_val(right_node[ind], tl, tr, m+1, r);
}

void upd(ll ind, ll tl, ll tr, ll l, ll r){
	extend(ind, l, 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;
		upd(left_node[ind], tl, tr, l, m);
		upd(right_node[ind], tl, tr, 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 << endl;
		}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