Submission #1242757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242757		Malix	Comparing Plants (IOI20_plants)	C++20	44 / 100	308 ms	33316 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=9000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,k;
vi a,st,R,lazy,ind;

void build(int x,int l,int r){
	if(l==r){
		st[x]=R[l];
		ind[x]=l;
		return;
	}
	int m=(l+r)/2;
	build(2*x,l,m);
	build(2*x+1,m+1,r);
	st[x]=min(st[2*x],st[2*x+1]);
	ind[x]=(st[x]==st[2*x]?ind[2*x]:ind[2*x+1]);
}

void push(int x){
	st[2*x]+=lazy[x];
	st[2*x+1]+=lazy[x];
	lazy[2*x]+=lazy[x];
	lazy[2*x+1]+=lazy[x];
	lazy[x]=0;
}

void update(int x,int l,int r,int u,int v,int val){
	if(u>v)return;
	if(u<0)exit(0);
	if(l!=r&&lazy[x])push(x);
	if(l==u&&r==v){
		st[x]+=val;
		lazy[x]=val;
		return;
	}
	int m=(l+r)/2;
	update(2*x,l,m,u,min(v,m),val);
	update(2*x+1,m+1,r,max(u,m+1),v,val);
	st[x]=min(st[2*x],st[2*x+1]);
	ind[x]=(st[x]==st[2*x]?ind[2*x]:ind[2*x+1]);
}

void init(int K, std::vector<int> r) {
	n=r.size();
	k=K;
	vi b;
	R=r;
	st.resize(4*n+1);
	ind.resize(4*n+1);
	lazy.resize(4*n+1,0);
	build(1,0,n-1);
	set<int> X;
	set<pi> Y;
	while(b.size()<n){
		while(st[1]==0){
			X.insert(ind[1]);
			auto it=X.find(ind[1]);
			auto nx=it;
			auto pr=it;
			if(nx!=X.end())nx++;
			if(pr!=X.begin())pr--;
			if(it!=X.begin()||nx!=X.end())Y.erase({*pr-*nx,*nx});
			if(it!=X.begin())Y.insert({*pr-*it,*it});
			if(nx!=X.end())Y.insert({*it-*nx,*nx});
			update(1,0,n-1,ind[1],ind[1],inf);
		}
		int u=*X.begin();
		if(-(Y.begin()->F)>k-1)u=Y.begin()->S;
		update(1,0,n-1,max(0,u-k+1),u-1,-1);
		update(1,0,n-1,u-k+1+n,n-1,-1);
		auto it=X.find(u);
		auto nx=it;
		auto pr=it;
		if(nx!=X.end())nx++;
		if(pr!=X.begin())pr--;
		if(it!=X.begin()||nx!=X.end())Y.insert({*pr-*nx,*nx});
		if(it!=X.begin())Y.erase({*pr-*it,*it});
		if(nx!=X.end())Y.erase({*it-*nx,*nx});
		X.erase(u);
		b.PB(u);
	}
	reverse(all(b));
	a.resize(n);
	REP(i,0,n)a[b[i]]=i;
}

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

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