Submission #338115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338115	2020-12-22T14:06:55 Z	Kerim	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	611 ms	262148 KB

apple

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
struct node {
	int mn,ans,lazy;
    node *l, *r;
    node(){l=r=NULL;}
};
const int B=1e9;
void merge(node *v,node *cep,node *sag){
	v->mn=min(cep->mn,sag->mn);v->ans=0;
	if(cep->mn==v->mn)
		v->ans+=cep->ans;
	if(sag->mn==v->mn)
		v->ans+=sag->ans;
}
void add(node *v,int val){
	v->lazy+=val;v->mn+=val;
}
void shift(node *v){
	if(v==NULL or v->lazy==0)
		return;
	add(v->l,v->lazy);
	add(v->r,v->lazy);
	v->lazy=0;
}
void inc(node *v,int l,int r,int x=1,int y=B){
	if(v==NULL or l>y or x>r or l>r)
		return;
	if(l<=x and y<=r){
		//cout<<"$ "<<x<<" "<<y<<endl;
		add(v,1);
		return;
	}
	int mid=(x+y)>>1;
	if(v->l==NULL){
		v->l=new node();
		v->l->ans=(mid-x+1);v->l->mn=v->l->lazy=0;
	}
	if(v->r==NULL){
		v->r=new node();
		v->r->ans=(y-mid);v->r->mn=v->r->lazy=0;
	}
	shift(v);
	inc(v->l,l,r,x,mid);
	inc(v->r,l,r,mid+1,y);
	merge(v,v->l,v->r);
}
node *ans;
void get(node *v,int l,int r,int x=1,int y=B){
	if(l>y or x>r or l>r or x>y)
		return;
	if(l<=x and y<=r){
		//cout<<x<<" "<<y<<" $ "<<v->mn<<" "<<v->ans<<endl;
		if(ans==NULL)
			ans=v;
		else{
			node *tmp=new node();
			merge(tmp,ans,v);ans=tmp;	
		}
		return;
	}
	int mid=(x+y)>>1;
	if(v->l==NULL){
		v->l=new node();
		v->l->ans=(mid-x+1);v->l->mn=v->l->lazy=0;
	}
	if(v->r==NULL){
		v->r=new node();
		v->r->ans=(y-mid);v->r->mn=v->r->lazy=0;
	}
	shift(v);
	get(v->l,l,r,x,mid);
	get(v->r,l,r,mid+1,y);
	merge(v,v->l,v->r);
}
int main(){
    //freopen("file.in", "r", stdin);
    node *root = new node();
	root->ans=B;root->lazy=root->mn=0;
    int q,c=0;
    scanf("%d",&q);
    while(q--){
    	int t;int l,r;
		scanf("%d%d%d",&t,&l,&r);l+=c;r+=c;
		if(t==2){
			//cout<<"inc "<<l<<" "<<r<<endl;
			inc(root,l,r);
		}
		else{
			//cout<<"get "<<l<<" "<<r<<endl;
			ans=NULL;get(root,l,r);c=ans->ans;
			if(ans->mn>0)c=0;c=(r-l+1)-c;
			printf("%d\n",c);
		}
    }
	return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:109:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  109 |    if(ans->mn>0)c=0;c=(r-l+1)-c;
      |    ^~
apple.cpp:109:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  109 |    if(ans->mn>0)c=0;c=(r-l+1)-c;
      |                     ^
apple.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
apple.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |   scanf("%d%d%d",&t,&l,&r);l+=c;r+=c;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	23 ms	9196 KB	Output is correct
5	Correct	28 ms	10732 KB	Output is correct
6	Correct	28 ms	11080 KB	Output is correct
7	Correct	29 ms	10732 KB	Output is correct
8	Correct	197 ms	67308 KB	Output is correct
9	Correct	401 ms	122476 KB	Output is correct
10	Correct	422 ms	131516 KB	Output is correct
11	Correct	422 ms	138604 KB	Output is correct
12	Correct	451 ms	141932 KB	Output is correct
13	Correct	430 ms	185836 KB	Output is correct
14	Correct	432 ms	186092 KB	Output is correct
15	Correct	611 ms	262144 KB	Output is correct
16	Runtime error	602 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-