Submission #426575

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426575	2021-06-14T07:01:10 Z	CSQ31	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	521 ms	207824 KB

apple

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
struct node{
	int lf,rg,sum,lazy;
	node *l,*r;
	node(int _lf,int _rg){
		l = nullptr;
		r = nullptr;
		sum = lazy = 0;
		lf = _lf;
		rg = _rg;
	}
	void pushdown(){
		int tm = (lf+rg)/2;
		if(l == nullptr)l = new node(lf,tm);
		if(r == nullptr)r = new node(tm+1,rg);
		if(lazy){
			lazy = 0;
			l->lazy = r->lazy = 1;
			l->sum = tm-lf+1;
			r->sum = rg-tm;
		}
	}
	void upd(int L,int R){
		if(L == lf && rg == R){
			sum = rg-lf+1;
			lazy = 1;
			return;
		}
		pushdown();
		int tm = (lf+rg)/2;
		if(R<=tm)l->upd(L,R);
		else if(tm<L)r->upd(L,R);
		else{
			l->upd(L,tm);
			r->upd(tm+1,R);
		}
		sum = l->sum + r->sum;
	}
	int query(int L,int R){
		if(L == lf && rg == R){
			return sum;
		}
		int tm = (lf+rg)/2;
		pushdown();
		if(R<=tm)return l->query(L,R);
		else if(tm<L)return r->query(L,R);
		else return l->query(L,tm) + r->query(tm+1,R);
	}
}*root = new node(1,1e9);
int main(){
	owo
	int m;
	cin>>m;
	int c=0;
	while(m--){
		int d,x,y;
		cin>>d>>x>>y;
		if(d==1){
			c = root->query(x+c,y+c);
			cout<<c<<'\n';	
		}else{
			root->upd(x+c,y+c);
		}
	}
	
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	14 ms	4968 KB	Output is correct
5	Correct	19 ms	6052 KB	Output is correct
6	Correct	17 ms	5800 KB	Output is correct
7	Correct	18 ms	5964 KB	Output is correct
8	Correct	153 ms	44472 KB	Output is correct
9	Correct	308 ms	77248 KB	Output is correct
10	Correct	316 ms	85424 KB	Output is correct
11	Correct	334 ms	91664 KB	Output is correct
12	Correct	321 ms	94500 KB	Output is correct
13	Correct	336 ms	109900 KB	Output is correct
14	Correct	278 ms	111064 KB	Output is correct
15	Correct	457 ms	201796 KB	Output is correct
16	Correct	430 ms	203144 KB	Output is correct
17	Correct	302 ms	114992 KB	Output is correct
18	Correct	286 ms	114812 KB	Output is correct
19	Correct	471 ms	207824 KB	Output is correct
20	Correct	521 ms	207660 KB	Output is correct