Submission #1064883

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

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#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){
	if(lazy[ind] == 0){return;}
	if(left_node[ind] == -1){return;}

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

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

	lazy[ind] = 0;
}


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


inline 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{
		pushdownwards(ind, l, r);

		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 << "\n";
		}else{
			upd(1, l+c, r+c, 0, MAX_N);
		}
	}
}

int main(){

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

	//st_time();
	solve();
	//pr_time();
}

• Subtask 1: 0 / 100