Submission #899905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899905	2024-01-07T09:23:55 Z	PotatoMan	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	255 ms	201872 KB

apple

#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod 1000000007
#define MAXN 100005
#define pii pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;
 
ll n,k,m,cur,z,q;
ll ans = 0;
string subtask;

struct node{
	int val,lazy,lc = -1,rc = -1,tl,tr;
	node(int pl,int pr){
		val = 0,lazy = 0,tl = pl, tr = pr, lc = -1,rc = -1;
	}
	void checklazy(int x){
		if(!x) return;
		val = tr-tl+1;
		lazy = x;
	}
};

struct segment_tree{
	vector<node> v;
	segment_tree(){
		v.push_back(node(1,1e9));
	}
	void prop(int x){
		if( v[x].tl != v[x].tr ){
			v[x].checklazy(v[x].lazy);
			int m = (v[x].tl+v[x].tr)/2;
			if(v[x].lc == -1){
				v[x].lc = v.size();
				v.push_back(node(v[x].tl,m));
			}
			if(v[x].rc == -1){
				v[x].rc = v.size();
				v.push_back(node(m+1,v[x].tr));
			}
			v[v[x].lc].checklazy(v[x].lazy);
			v[v[x].rc].checklazy(v[x].lazy);
			v[x].lazy = 0;
		}
	}
	void update(int l,int r,int x){
		if( l > v[x].tr || r < v[x].tl ) return;
		if( l <= v[x].tl && v[x].tr <= r ){
			v[x].checklazy(1);
			return;
		}
		prop(x);
		update(l,r,v[x].lc);
		update(l,r,v[x].rc);
		v[x].val = v[v[x].lc].val + v[v[x].rc].val;
	}
	int query(int l,int r,int x){
		if( l > v[x].tr || r < v[x].tl ) return 0;
		if( l <= v[x].tl && v[x].tr <= r ) {
			v[x].checklazy(v[x].lazy);
			return v[x].val;
		}
		prop(x);
		return query(l,r,v[x].lc)+query(l,r,v[x].rc);
	}
};

void solve(){
	cin>>n;
	segment_tree seg;
	cur = 0;
	while(n--){
		ll x,y,z;
		cin>>x>>y>>z;
		if( x == 1 ){
			ll k = seg.query(y+cur,z+cur,0);
			cout<<k<<"\n";
			cur = k;
		}
		else{
			seg.update(y+cur,z+cur,0);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	for(int i = 0 ; i < T ; i++){
		//cout<<"Case #"<<i+1<<": ";
		solve();
	}
	return 0;
}
 
/*
	misread -> missed subtask
	you thought u declared it huh?
	not i but x
	logical operator
	wrong example/proof
	thoroughly
	wrong variables
	thinking it wrong
	bruh just try some test case
	capitals ;-;
	wrong data structure lol
	count memory usement
	corner case
	oversized array
	orders
	statements
	size initializer
	while con
	map -> array
	wrong digits??
	swapped variables??
	check if theres any variabled
	that got declared twice
	find some pattern
	name collision
	constraints??!
	mod !!
	resets
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	11 ms	3644 KB	Output is correct
5	Correct	12 ms	3792 KB	Output is correct
6	Correct	12 ms	3820 KB	Output is correct
7	Correct	12 ms	5072 KB	Output is correct
8	Correct	76 ms	26036 KB	Output is correct
9	Correct	169 ms	51872 KB	Output is correct
10	Correct	163 ms	52388 KB	Output is correct
11	Correct	172 ms	52896 KB	Output is correct
12	Correct	175 ms	51724 KB	Output is correct
13	Correct	168 ms	103068 KB	Output is correct
14	Correct	157 ms	102628 KB	Output is correct
15	Correct	250 ms	200828 KB	Output is correct
16	Correct	242 ms	201872 KB	Output is correct
17	Correct	164 ms	103068 KB	Output is correct
18	Correct	167 ms	102884 KB	Output is correct
19	Correct	255 ms	201312 KB	Output is correct
20	Correct	240 ms	201840 KB	Output is correct