Submission #543609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543609	2022-03-31T01:18:23 Z	089487	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	390 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=(1<<30);
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;
    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")
      | 
apple.cpp: In member function 'void Vertex::update(int, int, int)':
apple.cpp:59:7: warning: unused variable 'middle' [-Wunused-variable]
   59 |   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	15 ms	8728 KB	Output is correct
5	Correct	22 ms	10656 KB	Output is correct
6	Correct	28 ms	10188 KB	Output is correct
7	Correct	20 ms	10536 KB	Output is correct
8	Correct	157 ms	78972 KB	Output is correct
9	Correct	303 ms	131216 KB	Output is correct
10	Correct	358 ms	150692 KB	Output is correct
11	Correct	338 ms	163444 KB	Output is correct
12	Correct	390 ms	169012 KB	Output is correct
13	Correct	321 ms	207704 KB	Output is correct
14	Correct	342 ms	209672 KB	Output is correct
15	Runtime error	361 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-