Submission #670656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670656	2022-12-09T19:53:34 Z	Koful123	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	343 ms	200168 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;
		}
		assert(seg[v].r < seg.size());
		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;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from apple.cpp:1:
apple.cpp: In member function 'void SegTree::push(int, int, int)':
apple.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   assert(seg[v].r < seg.size());

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	11 ms	3492 KB	Output is correct
5	Correct	13 ms	3516 KB	Output is correct
6	Correct	15 ms	3528 KB	Output is correct
7	Correct	14 ms	3536 KB	Output is correct
8	Correct	96 ms	25088 KB	Output is correct
9	Correct	202 ms	49792 KB	Output is correct
10	Correct	214 ms	49884 KB	Output is correct
11	Correct	209 ms	49840 KB	Output is correct
12	Correct	211 ms	49808 KB	Output is correct
13	Correct	221 ms	99392 KB	Output is correct
14	Correct	218 ms	99268 KB	Output is correct
15	Correct	338 ms	200024 KB	Output is correct
16	Correct	340 ms	200096 KB	Output is correct
17	Correct	219 ms	101400 KB	Output is correct
18	Correct	222 ms	101380 KB	Output is correct
19	Correct	339 ms	200076 KB	Output is correct
20	Correct	343 ms	200168 KB	Output is correct