Submission #670652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670652	2022-12-09T19:49:13 Z	Koful123	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	437 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

struct node{
	int sum,lazy,l,r,tl,tr;
	node(): sum(0), lazy(0), l(0), r(0), tl(1), tr(1e9) {};
};

struct SegTree{
	vector<node> seg;
	SegTree(){
		seg.pb(node());
	};
	void push(int v,int tl,int tr){
		int tm = (tl + tr) / 2;
		if(seg[v].l == 0){
			seg[v].l = seg.size();
			seg.pb(node());
			seg[seg[v].l].tl = tl;
			seg[seg[v].l].tr = tm;
		}
		if(seg[v].r == 0){
			seg[v].r = seg.size();
			seg.pb(node());
			seg[seg[v].r].tl = tm + 1;
			seg[seg[v].r].tr = tr;
		}
		if(!seg[v].lazy) return;
		seg[seg[v].r].lazy = seg[v].lazy;
		seg[seg[v].r].sum = seg[v].lazy * (tr - tm);	
		seg[seg[v].l].lazy = seg[v].lazy;
		seg[seg[v].l].sum = seg[v].lazy * (tm - tl + 1);	
		seg[v].lazy = 0;
	}
	void upd(int v,int l,int r,int tl,int tr,int x){
		if(tl > r || tr < l) return;
		if(tl >= l && tr <= r){
			seg[v].sum = (tr - tl + 1) * x; 
			seg[v].lazy = x;
			return;
		};
		push(v,tl,tr);
		int tm = (tl + tr) / 2;
		upd(seg[v].l,l,r,tl,tm,x), upd(seg[v].r,l,r,tm+1,tr,x);
		seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tl > r || tr < l) return 0;
		if(tl >= l && tr <= r){
			return seg[v].sum;
		}
		push(v,tl,tr);
		int tm = (tl + tr) / 2;
		return get(seg[v].l,tl,tm,l,r) + get(seg[v].r,tm+1,tr,l,r); 
	}
	int get(int l,int r){
		return get(0,1,1e9,l,r);
	}
};

void solve(){

	SegTree seg;

	int q,c = 0; cin >> q;
	for(int i = 0; i < q; i++){
		int ty,l,r; cin >> ty >> l >> r;
		if(ty == 2){
			seg.upd(0,l + c,r + c,1,1e9,1);
		}
		else{
			int res = seg.get(l+c,r+c);
			cout << res << endl; c = res;
		}
	}
}
 
signed main(){
 
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	13 ms	6724 KB	Output is correct
5	Correct	15 ms	6724 KB	Output is correct
6	Correct	15 ms	6724 KB	Output is correct
7	Correct	18 ms	6724 KB	Output is correct
8	Correct	119 ms	50296 KB	Output is correct
9	Correct	252 ms	100360 KB	Output is correct
10	Correct	251 ms	100028 KB	Output is correct
11	Correct	253 ms	100136 KB	Output is correct
12	Correct	264 ms	100076 KB	Output is correct
13	Correct	272 ms	199896 KB	Output is correct
14	Correct	278 ms	199988 KB	Output is correct
15	Runtime error	437 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-