Submission #1063364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063364		Itamar	Comparing Plants (IOI20_plants)	C++14	0 / 100	37 ms	5052 KiB

plants

#include<vector>
#define vi vector<int>
using namespace std;
#include<queue>
#include <set>
const int siz = 2e5+2;
int ans[siz];
int N,K;
vi R;
int dis(int a, int b){ // oriented
	if(b > a)return b-a;
	return b-a+N;
}
queue<int> q;

struct node{
	int l,r,mid,minir,plus;
	node* sl,*sr;
	node(int li, int ri){
		l = li, r = ri, mid = (l+r)/2,plus=0;
		if(l<r){
			sl = new node(l,mid);
			sr = new node(mid+1,r);
			minir = min(sl->minir,sr->minir);
		}else{
			minir = R[l];
		}
	}
	void push(){
		if(l==r)return;
		sl->minir+=plus;
		sr->minir+=plus;
		sl->plus+=plus;
		sr->plus+=plus;
		plus=0;
	}
	void update(int a, int b, int p){
		push();
		if(r < a || l > b)return;
		if(a <= l && b >= r){
			minir+=p;
			plus+=p;
		}else{
			sl->update(a,b,p);
			sr->update(a,b,p);
			minir = min(sl->minir,sr->minir);
		}
	}
	int find(){
     	push();
		if(l==r){
			if(minir<=0){
				return l;
			}
			else return 1e9;
		}
		if(sl->minir<=0){
			
			return sl->find();
		}
		else if(sr->minir <=0)return sr->find();
		else return 1e9;
	}
};
set<int> s;
node* seg;
bool check(int i){
	auto it = s.find(i);
	if(it == s.end())return 0;
	auto it2 = it;
	int j;
	if(it2!=s.begin())j = *(--it2);
	else j =  *(s.rbegin());
	if(*it2 == i){
		q.push(i);
		return 1;
	}
	if(dis(*it2,i)>=K ){
		q.push(i);
		return 1;
	}
	else{
		q.push(i);
		return 0;
	}
}
void ins(int i){ // he now has r[i]=0
	//auto it = s.find(i);
	s.insert(i);
	q.push(i);
}
int mod(int i){
	return (i+N)%N;
}
void er(int i){ // i was considered as a maximum
	auto it = s.find(i);
	if(i>=K-1){
		seg->update(i-K+1,i,-1);
	}else{
		seg->update(0,i,-1);
		seg->update(mod(i-K+1),N-1,-1);
	}
	auto it1 = it, it2 = it;
	it2++;
	it1--;
	
	s.erase(i);if(s.empty())return;
	if(it1 == s.end())it1 = s.begin();
	q.push(*it1);
	if(it2 == s.end())it2 = s.begin();
	q.push(*it2);
}
void init(int k, std::vector<int> r) {
	N = r.size(), K = k, R = r;
	 seg = new node(0,N-1);
	
	while(true){
		int f = seg->find();
		seg->update(f,f,1e9);
		if(f==1e9)break;
		ins(f);
		
	}
	for(int i : s)q.push(i);
	int ito = 1;
	vi vis(N);
	while(ito<=N){

		int i = q.front();
		//for(int j : s)if(check(j))i=j;
		q.pop();
		
		if(vis[i])continue;
		q.push(i);
		if(check(i)==0)continue;
		vis[i]=1;
		er(i);
		ans[i]=ito;
		ito++;
		while(true){
		int f = seg->find();
			seg->update(f,f,1e9);
		if(f==1e9)break;
		ins(f);
		q.push(f);
		}
	}
	/*for(int i = 0; i < N; i++){
		if(ans[i]==0){
			for(int j = 0; j < 2e9; j++){
				ans[i] = (ans[i]+1)%N;
			}
		}
	}*/
	int i =5;
	return;
}

int compare_plants(int x, int y) {
	if(ans[x]<ans[y])return 1;
	return -1;
}

Compilation message (stderr)

plants.cpp: In function 'bool check(int)':
plants.cpp:71:6: warning: variable 'j' set but not used [-Wunused-but-set-variable]
   71 |  int j;
      |      ^
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:155:6: warning: unused variable 'i' [-Wunused-variable]
  155 |  int i =5;
      |      ^

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