Submission #170381

#	Time	Username	Problem	Language	Result	Execution time	Memory
170381		workharder	Minerals (JOI19_minerals)	C++14	100 / 100	195 ms	7304 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const double RAT=1.618;
const int MAXN=86005;
int lo[MAXN],hi[MAXN],arr[MAXN],res[MAXN],n,bit[MAXN];
vector<int> mid[MAXN];

int query(int now){
	int ret=0;
	for(int i=now;i>0;i-=(i&(-i)))ret+=bit[i];
	return ret;
}

void update(int now,int val){
	for(int i=now;i<=n;i+=(i&(-i)))bit[i]+=val;
}

int binser(int x){
	int now=0;
	for(int i=17;i>=0;i--){
		if(now+(1<<i)<=n && bit[now+(1<<i)]<x){
			now+=(1<<i);
			x-=bit[now];
		}
	}
	return now+1;
}

int tengah(int x,int y){
	int L=query(x-1)+1,R=query(y),T;
	T=(3*L+2*R)/5;
	return binser(T);
}

void Solve(int N) {
	int prev=0,tmpL=1,tmpR=N+1,nxt,sudah=0,C=0;
	n=N;
	vector<int> v;
	for(int i=1;i<=2*N;i++)v.push_back(i);
	random_shuffle(v.begin(),v.end());
	for(auto i : v){
		if(tmpL==N+1 || Query(i)==prev){
			arr[tmpR]=i;
			lo[tmpR]=C+1;
			hi[tmpR]=tmpL-1;
			if(lo[tmpR]<hi[tmpR])mid[tengah(lo[tmpR],hi[tmpR])].push_back(tmpR);
			else{
				Answer(i,arr[tmpL-1]);
				update(tmpL-1,-1);
				arr[tmpL-1]=0;
				sudah++;
			}
			tmpR++;
			if(tmpL==tmpR-N)C=tmpL-1;
		}
		else{
			update(tmpL,1);
			arr[tmpL]=i;
			tmpL++;
			prev++;
		}
	}
	if(sudah==N)return;
	int prefix=0;
	while(sudah<N){
		for(int i=1;i<=N;i++){
			if(arr[i])prev=Query(arr[i]);
			while(!mid[i].empty()){
				int now=mid[i].back();
				mid[i].pop_back();
				nxt=Query(arr[now]);
				if(prefix){
					if(nxt==prev){   //sudah ada
						hi[now]=i;
						res[now]=i;
						if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							res[now]=binser(query(hi[now]));
							Answer(arr[now],arr[res[now]]);
							update(res[now],-1);
							arr[now]=0;arr[res[now]]=0;
						}
					}
					else{
						lo[now]=i+1;
						if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							res[now]=binser(query(hi[now]));
							Answer(arr[now],arr[res[now]]);
							update(res[now],-1);
							arr[now]=0;arr[res[now]]=0;
						}
					}
				}
				else{
					if(nxt==prev){
						lo[now]=i+1;
						if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							res[now]=binser(query(hi[now]));
							Answer(arr[now],arr[res[now]]);
							update(res[now],-1);
							arr[now]=0;arr[res[now]]=0;
						}
					}
					else{
						hi[now]=i;
						res[now]=i;
						if(query(hi[now])-query(lo[now]-1)>1)mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							res[now]=binser(query(hi[now]));
							Answer(arr[now],arr[res[now]]);
							update(res[now],-1);
							arr[now]=0;arr[res[now]]=0;
						}
					}
				}
				if(sudah==N)return;
				prev=nxt;
			}
		}
		prefix=1-prefix;
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10