oj.uz

답안 #360230

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
360230 2021-01-27T22:00:08 Z Kerim 식물 비교 (IOI20_plants) C++17
32 / 100
 2121 ms 65576 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] and 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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 42604 KB Output is correct
2 Correct 24 ms 42604 KB Output is correct
3 Correct 25 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 123 ms 45420 KB Output is correct
7 Correct 209 ms 46700 KB Output is correct
8 Correct 831 ms 56300 KB Output is correct
9 Correct 836 ms 56172 KB Output is correct
10 Correct 870 ms 56316 KB Output is correct
11 Correct 858 ms 56136 KB Output is correct
12 Correct 862 ms 56100 KB Output is correct
13 Correct 821 ms 58988 KB Output is correct
14 Correct 940 ms 59116 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 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 Correct 25 ms 42604 KB Output is correct
6 Correct 29 ms 42860 KB Output is correct
7 Correct 112 ms 46060 KB Output is correct
8 Correct 27 ms 42732 KB Output is correct
9 Correct 29 ms 42860 KB Output is correct
10 Correct 112 ms 46060 KB Output is correct
11 Correct 101 ms 45784 KB Output is correct
12 Correct 102 ms 46060 KB Output is correct
13 Correct 110 ms 46060 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 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 Correct 25 ms 42604 KB Output is correct
6 Correct 29 ms 42860 KB Output is correct
7 Correct 112 ms 46060 KB Output is correct
8 Correct 27 ms 42732 KB Output is correct
9 Correct 29 ms 42860 KB Output is correct
10 Correct 112 ms 46060 KB Output is correct
11 Correct 101 ms 45784 KB Output is correct
12 Correct 102 ms 46060 KB Output is correct
13 Correct 110 ms 46060 KB Output is correct
14 Correct 204 ms 47212 KB Output is correct
15 Correct 2111 ms 61932 KB Output is correct
16 Correct 206 ms 47212 KB Output is correct
17 Correct 2121 ms 62188 KB Output is correct
18 Correct 1070 ms 60908 KB Output is correct
19 Correct 1132 ms 60780 KB Output is correct
20 Correct 2062 ms 65576 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 42604 KB Output is correct
2 Correct 24 ms 42604 KB Output is correct
3 Correct 140 ms 45632 KB Output is correct
4 Correct 1027 ms 56232 KB Output is correct
5 Correct 1204 ms 56136 KB Output is correct
6 Incorrect 1524 ms 56196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 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 Correct 24 ms 42604 KB Output is correct
6 Correct 26 ms 42860 KB Output is correct
7 Incorrect 51 ms 43244 KB Output isn't correct
8 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 42732 KB Output is correct
4 Correct 23 ms 42604 KB Output is correct
5 Incorrect 28 ms 42732 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 42604 KB Output is correct
2 Correct 24 ms 42604 KB Output is correct
3 Correct 25 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 123 ms 45420 KB Output is correct
7 Correct 209 ms 46700 KB Output is correct
8 Correct 831 ms 56300 KB Output is correct
9 Correct 836 ms 56172 KB Output is correct
10 Correct 870 ms 56316 KB Output is correct
11 Correct 858 ms 56136 KB Output is correct
12 Correct 862 ms 56100 KB Output is correct
13 Correct 821 ms 58988 KB Output is correct
14 Correct 940 ms 59116 KB Output is correct
15 Correct 24 ms 42604 KB Output is correct
16 Correct 23 ms 42604 KB Output is correct
17 Correct 24 ms 42604 KB Output is correct
18 Correct 23 ms 42604 KB Output is correct
19 Correct 25 ms 42604 KB Output is correct
20 Correct 29 ms 42860 KB Output is correct
21 Correct 112 ms 46060 KB Output is correct
22 Correct 27 ms 42732 KB Output is correct
23 Correct 29 ms 42860 KB Output is correct
24 Correct 112 ms 46060 KB Output is correct
25 Correct 101 ms 45784 KB Output is correct
26 Correct 102 ms 46060 KB Output is correct
27 Correct 110 ms 46060 KB Output is correct
28 Correct 204 ms 47212 KB Output is correct
29 Correct 2111 ms 61932 KB Output is correct
30 Correct 206 ms 47212 KB Output is correct
31 Correct 2121 ms 62188 KB Output is correct
32 Correct 1070 ms 60908 KB Output is correct
33 Correct 1132 ms 60780 KB Output is correct
34 Correct 2062 ms 65576 KB Output is correct
35 Correct 23 ms 42604 KB Output is correct
36 Correct 24 ms 42604 KB Output is correct
37 Correct 140 ms 45632 KB Output is correct
38 Correct 1027 ms 56232 KB Output is correct
39 Correct 1204 ms 56136 KB Output is correct
40 Incorrect 1524 ms 56196 KB Output isn't correct
41 Halted 0 ms 0 KB -