oj.uz

답안 #338115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338115 2020-12-22T14:06:55 Z Kerim 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 611 ms 262148 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);
}
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

# 결과 실행 시간 메모리 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 -