Submission #1291649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291649		enzy	Comparing Plants (IOI20_plants)	C++20	0 / 100	1 ms	580 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int v[maxn], lz[4*maxn], pd[maxn], n, ja[maxn];
pair<int,int> seg[4*maxn];
void build(int id, int ini, int fim){
	if(ini==fim){
		seg[id].first=0; seg[id].second=ini;
		return;
	}
	int mid=(ini+fim)/2, e=2*id, d=2*id+1;
	build(e,ini,mid); build(d,mid+1,fim);
	lz[id]=0;
	seg[id]=min(seg[e],seg[d]);
}
void refresh(int id, int ini, int fim){
	if(ini!=fim){
		int e=2*id, d=2*id+1;
		lz[e]+=lz[id];
		lz[d]+=lz[id];
	}
	seg[id].first+=lz[id];
	lz[id]=0;
}
void update(int id, int ini, int fim, int l, int r, int val){
	refresh(id,ini,fim);
	if(ini>r||fim<l) return;
	if(l<=ini&&fim<=r){
		lz[id]+=val;
		refresh(id,ini,fim);
		return;
	}
	int mid=(ini+fim)/2, e=2*id, d=2*id+1;
	update(e,ini,mid,l,r,val); update(d,mid+1,fim,l,r,val);
	seg[id]=min(seg[e],seg[d]);
}
pair<int,int> query(int id, int ini, int fim, int l, int r){
	if(ini>r||fim<l) return {maxn,maxn};
	if(l<=ini&&fim<=r) return seg[id];
	int mid=(ini+fim)/2, e=2*id, d=2*id+1;
	return min(query(e,ini,mid,l,r),query(d,mid+1,fim,l,r));
}
int dist(int a, int b){
	if(a<b) return b-a;
	return b+1+(n-1-a);
}
void init(int k, vector<int> r){
	//cout << "iniciado" << endl;
	k--;
	n=r.size();
	build(1,0,n-1);
	for(int i=0;i<n;i++) update(1,0,n-1,i,i,r[i]);
	int cnt=maxn;
	set<int>s;
	vector<int>at, candidatos;
	while(!query(1,0,n-1,0,n-1).first){ // enquanto tem cara com 0
		int aux=query(1,0,n-1,0,n-1).second;
		update(1,0,n-1,aux,aux,2*maxn); // settando pra inf
		s.insert(aux);
		auto f=s.upper_bound(aux);
		if(f==s.end()) f=s.begin();
		int qm=*f;
		if(aux!=qm&&dist(aux,qm)<=k) pd[qm]=0; // vendo se bloqueio algm
		auto g=s.lower_bound(aux);
		if(g==s.begin()) g=s.end();
		g--;
		int ant=*g;
		if(ant==aux||dist(ant,aux)>k) pd[aux]=1; // vendo se algm me bloqueia
		candidatos.push_back(aux);
	}
	for(int x : candidatos){
		if(pd[x]){
			at.push_back(x);
			s.erase(x);
		}
	}
	// cout << "what " << at.size() << endl;
	while(query(1,0,n-1,0,n-1).first<maxn){
		// cout << "! ";
		// for(int x : at) cout << x << " ";
		// cout << endl;
		// cout << "? ";
		// for(int x : s) cout << x << " ";
		// cout << endl;
		candidatos.clear();
		for(int x : at){
			v[x]=cnt;
			if(x>=k) update(1,0,n-1,x-k,x-1,-1);
			else{
				update(1,0,n-1,0,x-1,-1);
				update(1,0,n-1,n-(k-x),n-1,-1);
			}
			while(!query(1,0,n-1,0,n-1).first){ // enquanto tem cara com 0
				int aux=query(1,0,n-1,0,n-1).second;
				update(1,0,n-1,aux,aux,2*maxn); // settando pra inf
				s.insert(aux);
				auto f=s.upper_bound(aux);
				if(f==s.end()) f=s.begin();
				int qm=*f;
				if(aux!=qm&&dist(aux,qm)<=k) pd[qm]=0; // vendo se bloqueio algm
				auto g=s.lower_bound(aux);
				if(g==s.begin()) g=s.end();
				g--;
				int ant=*g;
				if(ant==aux||dist(ant,aux)>k) pd[aux]=1; // vendo se algm me bloqueia
				candidatos.push_back(aux);
			}
		}
		for(int x : at){
			auto f=s.lower_bound(x);
			int aux=*f;
			if(f==s.begin()) f=s.end();
			f--;
			int ant=*f;
			if(dist(ant,aux)>k){
				candidatos.push_back(aux);
				pd[aux]=1;
			}
		}
		at.clear();
		for(int x : candidatos){
			if(pd[x]&&ja[x]==0){
				ja[x]++;
				at.push_back(x);
				s.erase(x);
			}
		}
		if(at.empty()){ // deu ciclo de inequacoes, ou seja, impossivel de decidir agr
			for(int x : s) at.push_back(x);
			s.clear();
		}
		cnt--;
	}
	// cout << query(1,0,n-1,0,n-1).first << endl;
	// cout << "finish" << endl;
}

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

• 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