Submission #1064820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1064820	2024-08-18T18:11:39 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;

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

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

	solve();
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	156756 KB	Output is correct
2	Correct	52 ms	156876 KB	Output is correct
3	Correct	53 ms	156796 KB	Output is correct
4	Correct	56 ms	157012 KB	Output is correct
5	Correct	63 ms	157008 KB	Output is correct
6	Correct	57 ms	157008 KB	Output is correct
7	Correct	59 ms	156848 KB	Output is correct
8	Correct	138 ms	157012 KB	Output is correct
9	Correct	265 ms	157332 KB	Output is correct
10	Correct	246 ms	157264 KB	Output is correct
11	Correct	279 ms	157268 KB	Output is correct
12	Correct	281 ms	157292 KB	Output is correct
13	Correct	220 ms	157264 KB	Output is correct
14	Correct	219 ms	157304 KB	Output is correct
15	Execution timed out	2401 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-