Submission #360216

#	Time	Username	Problem	Language	Result	Execution time	Memory
360216		Kerim	Comparing Plants (IOI20_plants)	C++17	27 / 100	979 ms	16740 KiB

plants

#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,lazy[MAXN<<2],arr[MAXN];
PII s[MAXN<<2];
void build(int nd=1,int x=0,int y=n-1){
	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 upd(int x,int y,int val){
	if(x<=y)inc(x,y,val);
	else inc(x,n-1,val),inc(0,y,val);
}
int get(){assert(s[1].ff==0);return s[1].ss;}
int vis[MAXN];
vector<int>tmp;
void zero(int i){	
	if(vis[i])return;vis[i]=1;	
	upd(i+1,(i+k-1)%n,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]);
}
void flex(int x,int y){
	if(x<=y)tap(x,y);
	else tap(x,n-1),tap(0,y);
}
void print(){
	for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
}
void init(int K, vector<int> r) {
	n=int(r.size());k=K;
	for(int i=0;i<n;i++)arr[i]=r[i];
	build();
	for(int i=0;i<n;i++)
		if(!arr[i])
			zero(i);
	for(int i=n-1;i>=0;i--){
		int res=get();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);
		flex(pre,res);flex(res,nex);
		tr(it,tmp)zero(*it);tmp.clear();
	}
}
int compare_plants(int x, int y) {
	int ans=0;
	ans+=(h[x]>h[y]);
	ans-=(h[x]<h[y]);
	return ans;
}

Compilation message (stderr)

plants.cpp: In function 'void zero(int)':
plants.cpp:61:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |  if(vis[i])return;vis[i]=1;
      |  ^~
plants.cpp:61:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   61 |  if(vis[i])return;vis[i]=1;
      |                   ^~~
plants.cpp: In function 'void print()':
plants.cpp:80:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'PII' {aka 'std::pair<int, int>'} [-Wformat=]
   80 |  for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
      |                              ~^   ~~~~
      |                               |      |
      |                               int    PII {aka std::pair<int, int>}
plants.cpp:80:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   80 |  for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
      |  ^~~
plants.cpp:80:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |  for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
      |                                         ^~~~
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:97:3: note: in expansion of macro 'tr'
   97 |   tr(it,tmp)zero(*it);tmp.clear();
      |   ^~
plants.cpp:97:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |   tr(it,tmp)zero(*it);tmp.clear();
      |                       ^~~

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25