Submission #1114418

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114418	2024-11-18T20:21:23 Z	nikolashami	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	172 ms	97608 KB

apple

#include <bits/stdc++.h>
using namespace std;

const int N=3e6;
int lc[N],rc[N],ans,m,c,id=1;
struct{int s=0,lz=0;}st[N];

void make(int&node){
	if(!node)node=++id;
}

void push(int node,int l,int r){
	if(!st[node].lz)
		return;
	int mid=(l+r)/2;
	st[lc[node]].s=mid-l+1;
	st[rc[node]].s=r-mid;
	st[lc[node]].lz=1;
	st[rc[node]].lz=1;
	st[node].lz=0;
}

void qry(int l,int r,int node=1,int tl=1,int tr=1e9){
	if(tl>=l&&tr<=r){
		ans+=st[node].s;
		return;
	}
	make(lc[node]);
	make(rc[node]);
	push(node,tl,tr);
	int mid=(tl+tr)/2;
	if(mid>=l)qry(l,r,lc[node],tl,mid);
	if(mid+1<=r)qry(l,r,rc[node],mid+1,tr);
}

void upd(int l,int r,int node=1,int tl=1,int tr=1e9){
	if(tl>=l&&tr<=r){
		st[node].s=tr-tl+1;	
		st[node].lz=1;
		return;
	}
	make(lc[node]);
	make(rc[node]);
	push(node,tl,tr);
	int mid=(tl+tr)/2;
	if(mid>=l)upd(l,r,lc[node],tl,mid);
	if(mid+1<=r)upd(l,r,rc[node],mid+1,tr);
	st[node].s=st[lc[node]].s+st[rc[node]].s;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>m;
    while(m--){
    	int tp,l,r;
    	cin>>tp>>l>>r;
    	if(tp==1){
    		ans=0;
    		qry(l+c,r+c);
    		c=ans;
    		cout<<ans<<'\n';
    	}else
    		upd(l+c,r+c);
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	508 KB	Output is correct
4	Correct	7 ms	1872 KB	Output is correct
5	Correct	9 ms	2128 KB	Output is correct
6	Correct	14 ms	2128 KB	Output is correct
7	Correct	8 ms	2128 KB	Output is correct
8	Correct	56 ms	15700 KB	Output is correct
9	Correct	108 ms	28508 KB	Output is correct
10	Correct	126 ms	32076 KB	Output is correct
11	Correct	150 ms	33144 KB	Output is correct
12	Correct	132 ms	33604 KB	Output is correct
13	Correct	113 ms	40440 KB	Output is correct
14	Correct	126 ms	40620 KB	Output is correct
15	Runtime error	172 ms	97608 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-