Submission #543607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543607	2022-03-31T01:06:48 Z	089487	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	460 ms	262144 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=1e9+7;
const int INF=1e18;
struct Vertex{
	int sum=0;
	int lx;
	int rx;
	int 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){
		extend();
		if(L<=lx&&rx<=R){
			lazy=val;
			if(val)sum=rx-lx;
			return ;
		}
		if(L>=rx||lx>=R) return ;
		int middle=(lx+rx)>>1;
		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){
		extend();
		if(L<=lx&&rx<=R) return sum;
		if(L>=rx||lx>=R) return 0;
		int s1,s2;
		s1=s2=0;
		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;
    int X=1;
    while(X<M) X*=2;
    Vertex*root=new Vertex(0,X);
    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")
      | 
apple.cpp: In member function 'void Vertex::update(long long int, long long int, long long int)':
apple.cpp:60:7: warning: unused variable 'middle' [-Wunused-variable]
   60 |   int middle=(lx+rx)>>1;
      |       ^~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	19 ms	11604 KB	Output is correct
5	Correct	25 ms	14024 KB	Output is correct
6	Correct	22 ms	13532 KB	Output is correct
7	Correct	22 ms	13932 KB	Output is correct
8	Correct	190 ms	106108 KB	Output is correct
9	Correct	399 ms	176760 KB	Output is correct
10	Correct	429 ms	202456 KB	Output is correct
11	Correct	460 ms	219604 KB	Output is correct
12	Correct	454 ms	226840 KB	Output is correct
13	Runtime error	392 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-