Submission #1065583

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065583	2024-08-19T09:38:27 Z	MrNanama	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	262144 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	156752 KB	Output is correct
2	Correct	55 ms	156768 KB	Output is correct
3	Correct	54 ms	156752 KB	Output is correct
4	Correct	64 ms	157120 KB	Output is correct
5	Correct	63 ms	157140 KB	Output is correct
6	Correct	62 ms	157176 KB	Output is correct
7	Correct	66 ms	157008 KB	Output is correct
8	Correct	146 ms	158032 KB	Output is correct
9	Correct	250 ms	159060 KB	Output is correct
10	Correct	256 ms	159060 KB	Output is correct
11	Correct	302 ms	159056 KB	Output is correct
12	Correct	254 ms	158928 KB	Output is correct
13	Correct	224 ms	159552 KB	Output is correct
14	Correct	215 ms	159576 KB	Output is correct
15	Execution timed out	2492 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-