Submission #543608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543608	2022-03-31T01:15:13 Z	089487	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	366 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:25:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   25 | const int INF=1e18;
      |               ^~~~
apple.cpp: In member function 'void Vertex::update(int, int, 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	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	16 ms	8884 KB	Output is correct
5	Correct	20 ms	10712 KB	Output is correct
6	Correct	18 ms	10288 KB	Output is correct
7	Correct	19 ms	10696 KB	Output is correct
8	Correct	153 ms	79356 KB	Output is correct
9	Correct	308 ms	131432 KB	Output is correct
10	Correct	326 ms	150628 KB	Output is correct
11	Correct	349 ms	163392 KB	Output is correct
12	Correct	349 ms	169056 KB	Output is correct
13	Correct	326 ms	209748 KB	Output is correct
14	Correct	335 ms	211740 KB	Output is correct
15	Runtime error	366 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-