Submission #960246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960246	2024-04-10T01:40:36 Z	pcc	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	158 ms	191012 KB

apple

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
const int inf = 1e9+10;
int N;

struct SEG{
#define ls seg[now].pl
#define rs seg[now].pr
#define mid ((l+r)>>1)
	struct node{
		int pl,pr,tag,cnt;
		node(){
			pl = pr = tag = cnt = 0;
		}
	};
	node seg[mxn*60];
	int ppp = 0;
	int newnode(){
		return ++ppp;
	}
	int modify(int now,int l,int r,int s,int e,int v){
		if(!now)now = newnode();
		if(l>=s&&e>=r){
			seg[now].tag += v;
			return now;
		}
		if(mid>=s)ls = modify(ls,l,mid,s,e,v);
		if(mid<e)rs = modify(rs,mid+1,r,s,e,v);
		seg[now].cnt = (seg[ls].tag?mid-l+1:seg[ls].cnt)+(seg[rs].tag?r-mid:seg[rs].cnt);
		return now;
	}
	int getval(int now,int l,int r,int s,int e){
		if(!now)return 0;
		if(seg[now].tag)return min(e,r)-max(s,l)+1;
		if(l>=s&&e>=r){
			return seg[now].cnt;
		}
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return getval(ls,l,mid,s,e)+getval(rs,mid+1,r,s,e);
	}
#undef ls
#undef rs
#undef mid
};

int Q;
SEG seg;
int rt = 0;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>Q;
	int C = 0;
	while(Q--){
		int t,s,e;
		cin>>t>>s>>e;
		s += C,e += C;
		if(t == 1){
			cout<<(C = seg.getval(rt,0,inf,s,e))<<'\n';
		}
		else{
			rt = seg.modify(rt,0,inf,s,e,1);
		}
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	188244 KB	Output is correct
2	Correct	69 ms	188144 KB	Output is correct
3	Correct	74 ms	188356 KB	Output is correct
4	Correct	75 ms	188324 KB	Output is correct
5	Correct	77 ms	188440 KB	Output is correct
6	Correct	79 ms	188308 KB	Output is correct
7	Correct	82 ms	188340 KB	Output is correct
8	Correct	105 ms	189328 KB	Output is correct
9	Correct	140 ms	190372 KB	Output is correct
10	Correct	138 ms	190292 KB	Output is correct
11	Correct	149 ms	190628 KB	Output is correct
12	Correct	158 ms	190396 KB	Output is correct
13	Correct	135 ms	190760 KB	Output is correct
14	Correct	138 ms	190808 KB	Output is correct
15	Correct	154 ms	190716 KB	Output is correct
16	Correct	158 ms	190736 KB	Output is correct
17	Correct	138 ms	190804 KB	Output is correct
18	Correct	145 ms	191012 KB	Output is correct
19	Correct	147 ms	190936 KB	Output is correct
20	Correct	148 ms	190800 KB	Output is correct