Submission #1064813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1064813	2024-08-18T18:05:21 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;}

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	156852 KB	Output is correct
2	Correct	48 ms	156760 KB	Output is correct
3	Correct	60 ms	157012 KB	Output is correct
4	Correct	71 ms	156956 KB	Output is correct
5	Correct	71 ms	157008 KB	Output is correct
6	Correct	72 ms	157012 KB	Output is correct
7	Correct	72 ms	156992 KB	Output is correct
8	Correct	183 ms	158024 KB	Output is correct
9	Correct	340 ms	159068 KB	Output is correct
10	Correct	335 ms	159060 KB	Output is correct
11	Correct	333 ms	159172 KB	Output is correct
12	Correct	346 ms	159152 KB	Output is correct
13	Correct	312 ms	159440 KB	Output is correct
14	Correct	314 ms	159568 KB	Output is correct
15	Execution timed out	2577 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-