oj.uz

답안 #360221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
360221 2021-01-27T21:10:53 Z Kerim 식물 비교 (IOI20_plants) C++17
14 / 100
 4000 ms 30828 KB 
#include "plants.h"
#include "bits/stdc++.h"
#define MAXN 200009
#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;}
int h[MAXN],n,k,arr[MAXN];
vector<int>tmp;
struct tree{
	PII s[MAXN<<2];int lazy[MAXN<<2];
	void build(int nd=1,int x=0,int y=n-1){
		lazy[nd]=0;
		if(x==y){
			s[nd]=mp(arr[x],x);
			return;
		}	
		int mid=(x+y)>>1;
		build(nd<<1,x,mid);
		build(nd<<1|1,mid+1,y);
		s[nd]=min(s[nd<<1],s[nd<<1|1]);
	}
	void shift(int nd){
		int &ret=lazy[nd];if(!ret)return;
		lazy[nd<<1]+=ret;s[nd<<1].ff+=ret;
		lazy[nd<<1|1]+=ret;s[nd<<1|1].ff+=ret;
		ret=0;	
	}
	void inc(int l,int r,int val,int nd=1,int x=0,int y=n-1){
		if(l>y or x>r)
			return;
		if(l<=x and y<=r){
			s[nd].ff+=val;
			lazy[nd]+=val;
			return;
		}
		shift(nd);
		int mid=(x+y)>>1;
		inc(l,r,val,nd<<1,x,mid);
		inc(l,r,val,nd<<1|1,mid+1,y);
		s[nd]=min(s[nd<<1],s[nd<<1|1]);
	}
	void print(int nd=1,int x=0,int y=n-1){
		if(x==y){
			printf("%d ",s[nd].ff);
			return;
		}shift(nd);
		int mid=(x+y)>>1;
		print(nd<<1,x,mid);
		print(nd<<1|1,mid+1,y);
		s[nd]=min(s[nd<<1],s[nd<<1|1]);
	}
	void tap(int l,int r,int nd=1,int x=0,int y=n-1){
		if(l>y or x>r or s[nd].ff>0)return;
		if(x==y){
			tmp.pb(x);
			return;
		}shift(nd);
		int mid=(x+y)>>1;
		tap(l,r,nd<<1,x,mid);
		tap(l,r,nd<<1|1,mid+1,y);
		s[nd]=min(s[nd<<1],s[nd<<1|1]);
	}
}ds[2];
void upd(int x,int y,int val,int bro=1){
	if(x<=y){
		ds[0].inc(x,y,val);
		if(bro)ds[1].inc(x,y,val);
	}
	else{ 
		ds[0].inc(x,n-1,val),ds[0].inc(0,y,val);
		if(bro)ds[1].inc(x,n-1,val),ds[1].inc(0,y,val);
	}
}
int get(){
	int a=ds[0].s[1].ff;
	int b=ds[0].s[1].ss;
	assert(a==0);return b;
}
int vis[MAXN];
void zero(int i){	
	if(vis[i])return;vis[i]=1;	
	//printf("zero %d\n",i);
	upd(i+1,(i+k-1)%n,1,0);
}
void flex(int x,int y){
	if(x<=y)ds[1].tap(x,y);
	else ds[1].tap(x,n-1),ds[1].tap(0,y);
}
int d(int x,int y){
	if(x>y)swap(x,y);
	return min(y-x,n-y+x);
}
set<PII>st;
int l[MAXN],r[MAXN];
void init(int K, vector<int> rz) {
	n=int(rz.size());k=K;
	for(int i=0;i<n;i++)arr[i]=rz[i];
	ds[0].build();ds[1].build();
	for(int i=0;i<n;i++)
		if(!arr[i])
			zero(i);
	for(int i=n-1;i>=0;i--){
		int res=get();assert(res>=0 and res<n);h[res]=i;
		//debug(res);
		int pre=(res-K+1+n)%n;
		int nex=(res+K-1)%n;
		upd(res,res,INF);
		upd(pre,res,-1);upd(res,nex,-1,0);
		flex(pre,res);flex(res,nex);
		//ds[0].print();puts("");
		tr(it,tmp)zero(*it);tmp.clear();
		//ds[1].print();
		//puts("");puts("");
	}
	int p=n-k+1;
	for(int i=p;i<n;i++)	
		st.insert(mp(h[i],i));
	for(int i=0;i<n;i++){
		__typeof((st).begin())it=st.lower_bound(mp(h[i],-1));
		if(it!=st.begin()){
			it--;l[i]=it->ss;
		}
		else
			l[i]=-1;
		st.erase(mp(h[p],p));p=(p+1)%n;
		st.insert(mp(h[i],i));
	}st.clear();p=k-2;
	for(int i=0;i<=p;i++)st.insert(mp(h[i],i));
	for(int i=n-1;i>=0;i--){
		__typeof((st).begin())it=st.lower_bound(mp(h[i],-1));
		if(it!=st.begin()){
			it--;r[i]=it->ss;
		}
		else
			r[i]=-1;
		st.erase(mp(h[p],p));p=(p-1+n)%n;
		st.insert(mp(h[i],i));
	}
}
int compare_plants(int x, int y) {
	if(d(x,y)<k){
		if(h[x]>h[y])return 1;
		else return -1;	
	}
	else{int a;
		/*
		printf("%d %d\n",x,y);
		for(int i=0;i<n;i++)printf("%d ",h[i]);puts("");
		for(int i=0;i<n;i++)printf("%d ",r[i]);puts("");
		for(int i=0;i<n;i++)printf("%d ",l[i]);puts("");*/
		a=x;while(~l[a] and a<=x)a=l[a];
		while(~l[a] and l[a]>y)a=l[a];
		if(d(a,y)<k and h[a]>h[y])return 1;
		
		a=x;while(~r[a] and r[a]<y)a=r[a];
		if(d(a,y)<k and h[a]>h[y])return 1;
		
		a=y;while(~l[a] and l[a]>x)a=l[a];
		if(d(a,x)<k and h[a]>h[x])return -1;
		
		a=y;while(~r[a] and y<=a)a=r[a];
		while(~r[a] and r[a]<x)a=r[a];
		if(d(a,x)<k and h[a]>h[x])return -1;
	}
	return 0;
}

Compilation message

plants.cpp: In function 'void zero(int)':
plants.cpp:95:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   95 |  if(vis[i])return;vis[i]=1;
      |  ^~
plants.cpp:95:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   95 |  if(vis[i])return;vis[i]=1;
      |                   ^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:10:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   10 | #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
      |                  ^~~
plants.cpp:125:3: note: in expansion of macro 'tr'
  125 |   tr(it,tmp)zero(*it);tmp.clear();
      |   ^~
plants.cpp:125:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  125 |   tr(it,tmp)zero(*it);tmp.clear();
      |                       ^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12908 KB Output is correct
2 Correct 7 ms 12928 KB Output is correct
3 Correct 8 ms 12908 KB Output is correct
4 Correct 8 ms 12908 KB Output is correct
5 Correct 7 ms 12928 KB Output is correct
6 Correct 74 ms 16748 KB Output is correct
7 Incorrect 205 ms 18924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12908 KB Output is correct
2 Correct 7 ms 12908 KB Output is correct
3 Correct 7 ms 12908 KB Output is correct
4 Correct 7 ms 12908 KB Output is correct
5 Correct 8 ms 12908 KB Output is correct
6 Correct 13 ms 13036 KB Output is correct
7 Correct 95 ms 16236 KB Output is correct
8 Correct 9 ms 12908 KB Output is correct
9 Correct 13 ms 13056 KB Output is correct
10 Correct 96 ms 16332 KB Output is correct
11 Correct 236 ms 16108 KB Output is correct
12 Correct 87 ms 16256 KB Output is correct
13 Correct 94 ms 16236 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12908 KB Output is correct
2 Correct 7 ms 12908 KB Output is correct
3 Correct 7 ms 12908 KB Output is correct
4 Correct 7 ms 12908 KB Output is correct
5 Correct 8 ms 12908 KB Output is correct
6 Correct 13 ms 13036 KB Output is correct
7 Correct 95 ms 16236 KB Output is correct
8 Correct 9 ms 12908 KB Output is correct
9 Correct 13 ms 13056 KB Output is correct
10 Correct 96 ms 16332 KB Output is correct
11 Correct 236 ms 16108 KB Output is correct
12 Correct 87 ms 16256 KB Output is correct
13 Correct 94 ms 16236 KB Output is correct
14 Correct 185 ms 17260 KB Output is correct
15 Correct 2048 ms 30700 KB Output is correct
16 Correct 189 ms 17388 KB Output is correct
17 Correct 2054 ms 30828 KB Output is correct
18 Execution timed out 4067 ms 22896 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12908 KB Output is correct
2 Correct 7 ms 12908 KB Output is correct
3 Incorrect 285 ms 15768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12908 KB Output is correct
2 Correct 7 ms 12908 KB Output is correct
3 Correct 7 ms 12908 KB Output is correct
4 Correct 7 ms 12908 KB Output is correct
5 Incorrect 8 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12928 KB Output is correct
2 Correct 8 ms 12908 KB Output is correct
3 Incorrect 7 ms 12908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12908 KB Output is correct
2 Correct 7 ms 12928 KB Output is correct
3 Correct 8 ms 12908 KB Output is correct
4 Correct 8 ms 12908 KB Output is correct
5 Correct 7 ms 12928 KB Output is correct
6 Correct 74 ms 16748 KB Output is correct
7 Incorrect 205 ms 18924 KB Output isn't correct
8 Halted 0 ms 0 KB -