Submission #349769

#	Time	Username	Problem	Language	Result	Execution time	Memory
349769		Bill_00	The Potion of Great Power (CEOI20_potion)	C++14	38 / 100	3082 ms	49772 KiB

potion

#include <bits/stdc++.h>
#define N 200000
#define M 100000
#define pb push_back
#define ff first
#define ss second
using namespace std;
int h[M],n;
vector<vector<int>>v[M];
int cnt[M],sz[N],c[M];
int q[M][2];
vector<pair<int,bool> >day[N];
void init(int nn,int d, int H[]){
	n=nn;
	for(int i=0;i<n;i++) h[i]=H[i];
}

void curseChanges(int u, int A[], int B[]){
	for(int i=1;i<=u;i++){
		++cnt[A[i-1]];
		++cnt[B[i-1]];
	}
	for(int i=0;i<n;i++){
		v[i].resize(cnt[i]+1);
		sz[i]=cnt[i];
		cnt[i]=0;
	}
	for(int i=1;i<=u;i++){
		q[i][0]=cnt[A[i-1]];
		q[i][1]=cnt[B[i-1]];
		cnt[A[i-1]]++;
		cnt[B[i-1]]++;
	}
	for(int i=1;i<=u;i++){
		int a=A[i-1],b=B[i-1];
		day[a].pb({i,0});
		day[b].pb({i,1});
		if(c[a]>sz[a] || c[b]>sz[b]) while(1);
		if(c[a]==0){
			v[a][c[a]].pb(b);
		}
		else{
			bool flag=0;
			for(int j:v[a][c[a]-1]){
				if(j==b){
					flag=1;
					continue;
				}
				v[a][c[a]].pb(j);
			}
			if(flag==0) v[a][c[a]].pb(b);
		}
		if(c[b]==0){
			v[b][c[b]].pb(a);
		}
		else{
			bool flag=0;
			for(int j:v[b][c[b]-1]){
				if(j==a){
					flag=1;
					continue;
				}
				v[b][c[b]].pb(j);
			}
			if(flag==0) v[b][c[b]].pb(a);
		}
		c[a]++;
		c[b]++;
	}
}

int question(int x, int y, int z) {
	pair<int,bool>pp={z,1};
	int ans=1e9;
	int id=upper_bound(day[x].begin(),day[x].end(),pp)-day[x].begin();
	--id;
	int e=day[x].size()-1;
	if(id<0 || id>e){
		return ans;
	}
	int a=q[day[x][id].ff][day[x][id].ss];
	id=upper_bound(day[y].begin(),day[y].end(),pp)-day[y].begin();
	--id;
	e=day[y].size()-1;
	if(id<0 || id>e){
		return ans;
	}
	int b=q[day[y][id].ff][day[y][id].ss];

	// cout << a << ' ' << b << '\n';
	if(v[x][a].size()==0 || v[y][b].size()==0){
		return ans;
	}
	vector<int>xx,yy;
	for(int V:v[y][b]){
		yy.pb(h[V]);
	}
	sort(yy.begin(),yy.end());
	for(int U:v[x][a]){
		int id=lower_bound(yy.begin(),yy.end(),h[U])-yy.begin();
		ans=min(ans,abs(h[U]-yy[max(0,id-1)]));
		int r=yy.size()-1;
		ans=min(ans,abs(yy[min(id,r)]-h[U]));
	}
	return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30