Submission #932272

#	Time	Username	Problem	Language	Result	Execution time	Memory
932272		pcc	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	126 ms	71096 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


int N,K;

struct node{
	int pl,pr,val,match;
	node(){
		pl = pr = val = match = 0;
	}
};
const int mxn = 1e6+10;
node arr[mxn*4];
int brr[mxn];
int pp = 1;
int rt = 1;
int sz = 1;

int newnode(){
	return ++pp;
}


void split(int now){
	sz++;
	arr[now].val--;
	int nxt = newnode();
	arr[nxt].val = arr[now].val;
	arr[arr[now].pr].pl = nxt;
	arr[nxt].pr = arr[now].pr;
	arr[nxt].pl = now;
	arr[now].pr = nxt;
	return;
}

void pv(int now){
	while(now){
		cout<<arr[now].val<<' ';now = arr[now].pr;
	}
	cout<<endl;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<=N;i++)cin>>brr[i];
	int now = rt;
	arr[rt].val = 30;
	for(int i = 1;i<=N;i++){
		while(arr[now].val<brr[i]){
			now = arr[now].pr;
		}
		while(arr[now].val>brr[i]){
			split(now);
		}
		//cout<<i<<' '<<now<<":"<<arr[now].val<<','<<arr[now].pr<<','<<brr[i]<<endl;
		//pv(rt);
		arr[now].match = true;
		now = arr[now].pr;
	}
	now = rt;
	while(now){
		while(sz<N+K&&!arr[now].match&&arr[now].val>0){
			split(now);
		}
		now = arr[now].pr;
	}
	now = rt;
	while(now){
		cout<<arr[now].val<<' ';
		now = arr[now].pr;
	}
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70