Submission #589067

#	Time	Username	Problem	Language	Result	Execution time	Memory
589067		pooyashams	The Potion of Great Power (CEOI20_potion)	C++14	17 / 100	72 ms	7052 KiB

potion

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int maxu = 2012;
const int inf = 1e9;

int n, D;
int H[maxn];
int U;
int A[maxu];
int B[maxu];

bool hasfrn[maxn];
int id[maxn];

int wfrn[maxu];
int fcnt = 0;

bool state[2][maxu];

void init(int N, int D, int H[])
{
	::n = N;
	::D = D;
	for(int i = 0; i < N; i++)
		::H[i] = H[i];
	fill(id, id+N, -1);
}

void curseChanges(int U, int A[], int B[])
{
	::U= U;
	for(int i = 0; i < U; i++)
	{
		::A[i] = A[i];
		::B[i] = B[i];
		hasfrn[A[i]] = true;
		hasfrn[B[i]] = true;
	}
	for(int i = 0; i < n; i++)
	{
		if(hasfrn[i])
			wfrn[fcnt++] = i;
	}
	sort(wfrn, wfrn+fcnt, [&](int i, int j){return H[i] < H[j];});
	for(int i = 0; i < fcnt; i++)
		id[wfrn[i]] = i;
}

int cfrs[2][maxu];

int question(int x, int y, int v)
{
	if(!hasfrn[x] and !hasfrn[y])
		return inf;
	memset(state, 0, sizeof(state));
	for(int i = 0; i < v; i++)
	{
		if(A[i] == x)
		{
			state[0][id[B[i]]] ^= 1;
			//cerr << "0 " << id[B[i]] << endl;
		}
		else if(B[i] == x)
		{
			state[0][id[A[i]]] ^= 1;
			//cerr << "0 " << id[A[i]] << endl;
		}
		if(A[i] == y)
		{
			state[1][id[B[i]]] ^= 1;
			//cerr << "1 " << id[B[i]] << endl;
		}
		else if(B[i] == y)
		{
			state[1][id[A[i]]] ^= 1;
			//cerr << "1 " << id[A[i]] << endl;
		}
	}
	int xc = 0;
	int yc = 0;
	for(int i = 0; i < fcnt; i++)
	{
		if(state[0][i])
			cfrs[0][xc++] = wfrn[i];
		if(state[1][i])
			cfrs[1][yc++] = wfrn[i];
	}
	//for(int i = 0; i < xc; i++)
	//	cerr << cfrs[0][i] << " ";
	//cerr << endl;
	//for(int i = 0; i < yc; i++)
	//	cerr << cfrs[1][i] << " ";
	//cerr << endl;
	int p = 0;
	int ans = inf;
	for(int i = 0; i < xc; i++)
	{
		while(p < yc and H[cfrs[1][p]] < H[cfrs[0][i]])
			p++;
		if(p > 0)
			ans = min(ans, abs(H[cfrs[0][i]] - H[cfrs[1][p-1]]) );
		if(p < yc)
			ans = min(ans, abs(H[cfrs[0][i]] - H[cfrs[1][p]]) );
	}
	return ans;
}

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