Submission #969373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969373	2024-04-25T04:28:20 Z	tamir1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	331 ms	207896 KB

apple

#include<bits/stdc++.h>
#define ll int
#define md (r+l)/2
using namespace std;
ll m,i,x,y,d,c,ans,mid;
struct node{
	node *le,*ri;
	ll val,lazy,l,r;
	void create(ll x,ll y){
		val=0;
		lazy=0;
		l=x;
		r=y;
		if(l==r) return;
		le=NULL;
		ri=NULL;
	}
	void fix(){          
		if(le==NULL){
			le=new node;
			le->create(l,md);
		}
		if(ri==NULL){
			ri=new node;
			ri->create(md+1,r);
		}
		if(lazy==0) return;
		le->val=le->r-le->l+1;
		ri->val=ri->r-ri->l+1;
		le->lazy=lazy;
		ri->lazy=lazy;
		lazy=0;
	}
	ll query(ll x,ll y){
		if(l>y || r<x) return 0;
		if(l>=x && r<=y) return val;
		fix();
		return le->query(x,y)+ri->query(x,y);
	}
	void update(ll x,ll y){
		if(l>y || r<x) return;
		if(l>=x && r<=y){
			val=r-l+1;
			lazy=1;
			return;
		}
		fix();
		le->update(x,y);
		ri->update(x,y);
		val=le->val+ri->val;
	}
} s;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> m;
	s.create(1,1e9);
	for(i=1;i<=m;i++){
		cin >> d >> x >> y;
		if(d==1){
			ans=s.query(x+c,y+c);
			cout << ans << "\n";
			c=ans;
		}
		else{
			s.update(x+c,y+c);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	12 ms	4956 KB	Output is correct
5	Correct	13 ms	5976 KB	Output is correct
6	Correct	12 ms	5724 KB	Output is correct
7	Correct	12 ms	5884 KB	Output is correct
8	Correct	91 ms	43856 KB	Output is correct
9	Correct	193 ms	75600 KB	Output is correct
10	Correct	200 ms	83792 KB	Output is correct
11	Correct	207 ms	89832 KB	Output is correct
12	Correct	203 ms	92756 KB	Output is correct
13	Correct	210 ms	107864 KB	Output is correct
14	Correct	186 ms	108956 KB	Output is correct
15	Correct	318 ms	201708 KB	Output is correct
16	Correct	324 ms	203136 KB	Output is correct
17	Correct	192 ms	114968 KB	Output is correct
18	Correct	200 ms	114840 KB	Output is correct
19	Correct	317 ms	207764 KB	Output is correct
20	Correct	331 ms	207896 KB	Output is correct