Submission #1064895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1064895	2024-08-18T19:00:25 Z	MrNanama	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	262144 KB

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

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	156756 KB	Output is correct
2	Correct	48 ms	156908 KB	Output is correct
3	Correct	48 ms	156900 KB	Output is correct
4	Correct	57 ms	157040 KB	Output is correct
5	Correct	60 ms	157008 KB	Output is correct
6	Correct	63 ms	157196 KB	Output is correct
7	Correct	61 ms	157000 KB	Output is correct
8	Correct	140 ms	158040 KB	Output is correct
9	Correct	253 ms	158952 KB	Output is correct
10	Correct	272 ms	159056 KB	Output is correct
11	Correct	247 ms	159060 KB	Output is correct
12	Correct	247 ms	159056 KB	Output is correct
13	Correct	222 ms	159420 KB	Output is correct
14	Correct	206 ms	159316 KB	Output is correct
15	Execution timed out	2535 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-