Submission #707896

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
707896	2023-03-10T11:30:07 Z	Koful123	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	337 ms	200076 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;
			
			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:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	12 ms	3612 KB	Output is correct
5	Correct	14 ms	3648 KB	Output is correct
6	Correct	14 ms	3712 KB	Output is correct
7	Correct	14 ms	3656 KB	Output is correct
8	Correct	99 ms	25812 KB	Output is correct
9	Correct	212 ms	51036 KB	Output is correct
10	Correct	216 ms	50872 KB	Output is correct
11	Correct	227 ms	50816 KB	Output is correct
12	Correct	220 ms	50988 KB	Output is correct
13	Correct	218 ms	101480 KB	Output is correct
14	Correct	222 ms	101324 KB	Output is correct
15	Correct	336 ms	200076 KB	Output is correct
16	Correct	335 ms	200072 KB	Output is correct
17	Correct	218 ms	101396 KB	Output is correct
18	Correct	221 ms	101400 KB	Output is correct
19	Correct	329 ms	199988 KB	Output is correct
20	Correct	337 ms	200036 KB	Output is correct