Submission #543613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543613	2022-03-31T01:58:49 Z	089487	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	448 ms	209456 KB

apple

#pragma GCC optimzize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
//#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=n;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int M=(1<<30);
struct Vertex{
	int sum=0;
	int lx;
	int rx;
	bool lazy=0;
	Vertex*l=nullptr;
	Vertex*r=nullptr;
	Vertex(int a,int b) : lx(a),rx(b){
	}
	void extend(){
		if(!l&&lx+1<rx){
			int middle=(lx+rx)>>1;
			l=new Vertex(lx,middle);
			r=new Vertex(middle,rx);
		}
	}
	void push(){
		if(lazy&&lx+1<rx){
			int middle=(lx+rx)>>1;
			l->lazy=lazy;
			l->sum=rx-middle;
			r->lazy=lazy;
			r->sum=middle-lx;
			lazy=0;
		}
	}
	void update(int L,int R,int val){
	
		if(L<=lx&&rx<=R){
			lazy=val;
			if(val)sum=rx-lx;
			return ;
		}
		if(L>=rx||lx>=R) return ;
		extend();
		push();
		if(l){
			l->update(L,R,val);
		}
		if(r) r->update(L,R,val);
		sum=l->sum+r->sum;
	//	debug("[",lx,rx,"]:",sum);
	}
	int query(int L,int R){
		
		if(L<=lx&&rx<=R) return sum;
		if(L>=rx||lx>=R) return 0;
		int s1,s2;
		s1=s2=0;
		extend();
		push();
		if(l) s1=l->query(L,R);
		if(r) s2=r->query(L,R);
		return s1+s2;
	}
};
signed main(){
    quick
    int m;
    cin>>m;
    Vertex*root=new Vertex(0,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{
			//debug(x+C,y+C+1);
			root->update(x+C,++y+C,1);
		}
	}
    return 0;
}

Compilation message

apple.cpp:1: warning: ignoring '#pragma GCC optimzize' [-Wunknown-pragmas]
    1 | #pragma GCC optimzize("Ofast,no-stack-protector")
      |

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	14 ms	5028 KB	Output is correct
5	Correct	17 ms	6148 KB	Output is correct
6	Correct	14 ms	5896 KB	Output is correct
7	Correct	15 ms	6000 KB	Output is correct
8	Correct	114 ms	44636 KB	Output is correct
9	Correct	228 ms	75468 KB	Output is correct
10	Correct	279 ms	85064 KB	Output is correct
11	Correct	251 ms	91348 KB	Output is correct
12	Correct	276 ms	94200 KB	Output is correct
13	Correct	273 ms	109072 KB	Output is correct
14	Correct	236 ms	110104 KB	Output is correct
15	Correct	399 ms	203444 KB	Output is correct
16	Correct	448 ms	204940 KB	Output is correct
17	Correct	242 ms	115672 KB	Output is correct
18	Correct	232 ms	115816 KB	Output is correct
19	Correct	414 ms	209456 KB	Output is correct
20	Correct	369 ms	209384 KB	Output is correct