Submission #338120

# Submission time Handle Problem Language Result Execution time Memory
338120 2020-12-22T14:13:26 Z Kerim Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
585 ms 207852 KB
#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);
}
PII ans[22];int p;
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;
		ans[p++]=mp(v->mn,v->ans);
		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;
			p=0;get(root,l,r);int mn=INF;
			for(int i=0;i<p;i++)
				umin(mn,ans[i].ff);
			if(mn>0)
				c=r-l+1;
			else{
				c=(r-l+1);
				for(int i=0;i<p;i++)
					if(ans[i].ff==0)
						c-=ans[i].ss;	
			}
			printf("%d\n",c);
		}
    }
	return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
apple.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   scanf("%d%d%d",&t,&l,&r);l+=c;r+=c;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
# 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 18 ms 4940 KB Output is correct
5 Correct 22 ms 5868 KB Output is correct
6 Correct 26 ms 5652 KB Output is correct
7 Correct 22 ms 5868 KB Output is correct
8 Correct 183 ms 43756 KB Output is correct
9 Correct 356 ms 75628 KB Output is correct
10 Correct 373 ms 83820 KB Output is correct
11 Correct 374 ms 89904 KB Output is correct
12 Correct 382 ms 92780 KB Output is correct
13 Correct 344 ms 108012 KB Output is correct
14 Correct 394 ms 109036 KB Output is correct
15 Correct 540 ms 200684 KB Output is correct
16 Correct 523 ms 203244 KB Output is correct
17 Correct 362 ms 114940 KB Output is correct
18 Correct 352 ms 115052 KB Output is correct
19 Correct 535 ms 207852 KB Output is correct
20 Correct 585 ms 207792 KB Output is correct