Submission #670655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670655	2022-12-09T19:52:59 Z	Koful123	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	418 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;
		}
		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(long long int, long long int, long long int)':
apple.cpp:35:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   assert(seg[v].r < seg.size());

Subtask #1

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	14 ms	6628 KB	Output is correct
5	Correct	17 ms	6576 KB	Output is correct
6	Correct	16 ms	6596 KB	Output is correct
7	Correct	16 ms	6560 KB	Output is correct
8	Correct	124 ms	49708 KB	Output is correct
9	Correct	251 ms	99152 KB	Output is correct
10	Correct	271 ms	99204 KB	Output is correct
11	Correct	268 ms	99056 KB	Output is correct
12	Correct	266 ms	99008 KB	Output is correct
13	Correct	290 ms	197868 KB	Output is correct
14	Correct	284 ms	197844 KB	Output is correct
15	Runtime error	418 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-