oj.uz

Submission #360228

# Submission time Handle Problem Language Result Execution time Memory
360228 2021-01-27T21:55:43 Z Kerim Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 65516 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];
		}
}
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){
	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

# Verdict Execution time Memory 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 23 ms 42604 KB Output is correct
5 Correct 23 ms 42604 KB Output is correct
6 Correct 108 ms 45620 KB Output is correct
7 Correct 193 ms 46728 KB Output is correct
8 Correct 739 ms 56172 KB Output is correct
9 Correct 766 ms 56300 KB Output is correct
10 Correct 916 ms 56172 KB Output is correct
11 Correct 2893 ms 56184 KB Output is correct
12 Execution timed out 4064 ms 59116 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42732 KB Output is correct
2 Correct 24 ms 42604 KB Output is correct
3 Correct 27 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 29 ms 42860 KB Output is correct
7 Correct 112 ms 46060 KB Output is correct
8 Correct 25 ms 42736 KB Output is correct
9 Correct 30 ms 42860 KB Output is correct
10 Correct 113 ms 46060 KB Output is correct
11 Correct 105 ms 45804 KB Output is correct
12 Correct 104 ms 46060 KB Output is correct
13 Correct 110 ms 46080 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42732 KB Output is correct
2 Correct 24 ms 42604 KB Output is correct
3 Correct 27 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 29 ms 42860 KB Output is correct
7 Correct 112 ms 46060 KB Output is correct
8 Correct 25 ms 42736 KB Output is correct
9 Correct 30 ms 42860 KB Output is correct
10 Correct 113 ms 46060 KB Output is correct
11 Correct 105 ms 45804 KB Output is correct
12 Correct 104 ms 46060 KB Output is correct
13 Correct 110 ms 46080 KB Output is correct
14 Correct 203 ms 47212 KB Output is correct
15 Correct 2087 ms 61956 KB Output is correct
16 Correct 202 ms 47212 KB Output is correct
17 Correct 2102 ms 62060 KB Output is correct
18 Correct 1055 ms 61036 KB Output is correct
19 Correct 1115 ms 61036 KB Output is correct
20 Correct 2032 ms 65516 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42604 KB Output is correct
2 Correct 23 ms 42604 KB Output is correct
3 Correct 155 ms 45548 KB Output is correct
4 Correct 3987 ms 56044 KB Output is correct
5 Correct 1774 ms 59372 KB Output is correct
6 Incorrect 1628 ms 59500 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory 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 23 ms 42604 KB Output is correct
5 Correct 24 ms 42604 KB Output is correct
6 Correct 26 ms 42732 KB Output is correct
7 Incorrect 46 ms 43244 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory 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 23 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

# Verdict Execution time Memory 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 23 ms 42604 KB Output is correct
5 Correct 23 ms 42604 KB Output is correct
6 Correct 108 ms 45620 KB Output is correct
7 Correct 193 ms 46728 KB Output is correct
8 Correct 739 ms 56172 KB Output is correct
9 Correct 766 ms 56300 KB Output is correct
10 Correct 916 ms 56172 KB Output is correct
11 Correct 2893 ms 56184 KB Output is correct
12 Execution timed out 4064 ms 59116 KB Time limit exceeded
13 Halted 0 ms 0 KB -