oj.uz

답안 #360229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
360229 2021-01-27T21:59:16 Z Kerim 식물 비교 (IOI20_plants) C++17
27 / 100
 2151 ms 65540 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;	
	ds[1].inc(i,i,INF);
	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;
const int LOG=19;
int l[MAXN],r[MAXN],pre[MAXN],suf[MAXN];
int A[MAXN][LOG],B[MAXN][LOG];
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;
		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);
		tr(it,tmp)zero(*it);tmp.clear();
	}
	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));
	}
	for(int i=0;i<n;i++){
		if(l[i]==-1)pre[i]=i;
		else if(l[i]<i)pre[i]=pre[l[i]];
		else pre[i]=l[i];
	}
	for(int i=n-1;i>=0;i--){
		if(r[i]==-1)suf[i]=i;
		else if(i<r[i])suf[i]=suf[r[i]];
		else suf[i]=r[i];
	}
	memset(A,-1,sizeof A);
	memset(B,-1,sizeof B);
	for(int i=0;i<n;i++){
		A[i][0]=l[i];
		B[i][0]=r[i];
	}
	for(int j=1;j<LOG;j++)
		for(int i=0;i<n;i++){
			if(~A[i][j-1] and A[i][j-1]>l[A[i][j-1]])
				A[i][j]=A[A[i][j-1]][j-1];	
			if(~B[i][j-1] and B[i][j-1]<r[B[i][j-1]])
				B[i][j]=B[B[i][j-1]][j-1];
		}
}
int cep(int x,int y){
	for(int j=LOG-1;j>=0;j--)
		if(A[x][j]>y)
			x=A[x][j];
	//while(x>l[x] and l[x]>y)x=l[x];
	return x;	
}
int sag(int x,int y){
	for(int j=LOG-1;j>=0;j--)
		if(B[x][j]<y)
			x=B[x][j];
	//while(r[x]<y and x<r[x])x=r[x];
	return x;
}
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;
		a=pre[x];if(a==y)return 1;a=cep(a,y);
		if(d(a,y)<k and h[a]>h[y])return 1;
		a=sag(x,y);if(d(a,y)<k and h[a]>h[y])return 1;
		a=cep(y,x);if(d(a,x)<k and h[a]>h[x])return -1;
		a=suf[y];if(a==x)return -1;a=sag(a,x);
		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 23 ms 42604 KB Output is correct
2 Correct 23 ms 42604 KB Output is correct
3 Correct 24 ms 42604 KB Output is correct
4 Correct 23 ms 42604 KB Output is correct
5 Incorrect 23 ms 42604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 42604 KB Output is correct
2 Correct 24 ms 42604 KB Output is correct
3 Correct 23 ms 42604 KB Output is correct
4 Correct 24 ms 42604 KB Output is correct
5 Correct 24 ms 42604 KB Output is correct
6 Correct 30 ms 42860 KB Output is correct
7 Correct 115 ms 46060 KB Output is correct
8 Correct 25 ms 42732 KB Output is correct
9 Correct 29 ms 42860 KB Output is correct
10 Correct 113 ms 46060 KB Output is correct
11 Correct 102 ms 45804 KB Output is correct
12 Correct 102 ms 46060 KB Output is correct
13 Correct 112 ms 46060 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 42604 KB Output is correct
2 Correct 24 ms 42604 KB Output is correct
3 Correct 23 ms 42604 KB Output is correct
4 Correct 24 ms 42604 KB Output is correct
5 Correct 24 ms 42604 KB Output is correct
6 Correct 30 ms 42860 KB Output is correct
7 Correct 115 ms 46060 KB Output is correct
8 Correct 25 ms 42732 KB Output is correct
9 Correct 29 ms 42860 KB Output is correct
10 Correct 113 ms 46060 KB Output is correct
11 Correct 102 ms 45804 KB Output is correct
12 Correct 102 ms 46060 KB Output is correct
13 Correct 112 ms 46060 KB Output is correct
14 Correct 205 ms 47340 KB Output is correct
15 Correct 2111 ms 62188 KB Output is correct
16 Correct 207 ms 47340 KB Output is correct
17 Correct 2151 ms 61988 KB Output is correct
18 Correct 1079 ms 61036 KB Output is correct
19 Correct 1127 ms 60908 KB Output is correct
20 Correct 2053 ms 65540 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 42604 KB Output is correct
2 Correct 23 ms 42604 KB Output is correct
3 Incorrect 154 ms 45548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 42604 KB Output is correct
2 Correct 23 ms 42604 KB Output is correct
3 Correct 23 ms 42604 KB Output is correct
4 Correct 24 ms 42604 KB Output is correct
5 Incorrect 27 ms 42732 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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