oj.uz

Submission #360216

# Submission time Handle Problem Language Result Execution time Memory
360216 2021-01-27T20:09:37 Z Kerim Comparing Plants (IOI20_plants) C++17
27 / 100
 979 ms 16740 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,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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 236 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 75 ms 3564 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 76 ms 3584 KB Output is correct
11 Correct 70 ms 3436 KB Output is correct
12 Correct 72 ms 3564 KB Output is correct
13 Correct 75 ms 3564 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 236 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 75 ms 3564 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 76 ms 3584 KB Output is correct
11 Correct 70 ms 3436 KB Output is correct
12 Correct 72 ms 3564 KB Output is correct
13 Correct 75 ms 3564 KB Output is correct
14 Correct 126 ms 4460 KB Output is correct
15 Correct 979 ms 12908 KB Output is correct
16 Correct 128 ms 6636 KB Output is correct
17 Correct 979 ms 16620 KB Output is correct
18 Correct 626 ms 16740 KB Output is correct
19 Correct 622 ms 16492 KB Output is correct
20 Correct 876 ms 16620 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Runtime error 2 ms 492 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -