Submission #912246

#	Time	Username	Problem	Language	Result	Execution time	Memory
912246		pcc	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	1118 ms	44692 KiB

potion

#include <bits/stdc++.h>
#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>

using namespace std;
const int inf = 1e9;
const int mxn = 1e5+10;
int arr[mxn];
int N,D,U;
pii ev[mxn];
vector<ll> bit[mxn];

void init(int NN, int DD, int H[]) {
	N = NN,D = D;
	for(int i = 0;i<N;i++)arr[i] = H[i];
	return;
}

void modify(int p,ll v){
	for(;p<mxn;p+=p&-p){
		bit[p].push_back(v);
	}
	return;
}

void curseChanges(int UU, int A[], int B[]) {
	U = UU;
	for(int i = 1;i<=U;i++){
		ev[i] = make_pair(A[i-1],B[i-1]);
		modify(i,1ll*ev[i].fs*mxn+ev[i].sc);
		modify(i,1ll*ev[i].sc*mxn+ev[i].fs);
	}
	for(int i = 1;i<=U;i++){
		vector<ll> tmp;
		swap(tmp,bit[i]);
		sort(tmp.begin(),tmp.end());
		for(auto &j:tmp){
			if(!bit[i].empty()&&bit[i].back() == j)bit[i].pop_back();
			else bit[i].push_back(j);
		}
		//cout<<i<<":";for(auto &j:bit[i])cout<<j<<',';cout<<endl;
	}
	return;
}

vector<int> getval(int p,int tar){
	ll s = 1ll*tar*mxn,e = 1ll*tar*mxn+mxn-1;
	vector<int> re;
	for(;p>0;p-= p&-p){
		auto lit = lower_bound(bit[p].begin(),bit[p].end(),s);
		auto rit = upper_bound(bit[p].begin(),bit[p].end(),e);
		for(auto it = lit;it != rit;it++){
			re.push_back(*it-1ll*tar*mxn);
		}
	}
	vector<int> tmp;
	swap(tmp,re);
	sort(tmp.begin(),tmp.end());
	for(auto &i:tmp){
		if(!re.empty()&&re.back() == i)re.pop_back();
		else re.push_back(i);
	}
	return re;
}

int question(int x, int y, int t) {
	auto v1 = getval(t,x);
	auto v2 = getval(t,y);
	/*
	for(auto &i:v1)cout<<i<<',';cout<<endl;
	for(auto &i:v2)cout<<i<<',';cout<<endl;

   */
	for(auto &i:v1)i = arr[i];
	for(auto &i:v2)i = arr[i];
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	int ans = 1e9;
	for(auto &i:v1){
		auto it = lower_bound(v2.begin(),v2.end(),i);
		if(it != v2.end())ans = min(ans,abs(*it-i));
		if(it != v2.begin()){
			it--;
			ans = min(ans,abs(*it-i));
		}
	}
	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