제출 #1242721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242721		Malix	식물 비교 (IOI20_plants)	C++20	0 / 100	30 ms	3540 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);
	while(b.size()<n){
		deque<int> c;
		int x=st[1];
		while(x==st[1]){
			c.PB(ind[1]);
			update(1,0,n-1,ind[1],ind[1],inf-x);
		}
		int y=0;
		while(y+1<c.size()&&c[y]+k-1>=c[y+1])y++;
		if(y!=c.size()-1){
			y++;
			while(y--){
				c.PB(c.front());
				c.pop_front();
			}
		}
		for(auto u:c)b.PB(u);
		for(auto u:c){
			update(1,0,n-1,max(0,u-k+1),u-1,-1);
			update(1,0,n-1,(u-k+1+n)%n,n-1,-1);
		}
	}
	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: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25