Submission #1281916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281916		banban	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	368 ms	40960 KiB

potion

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

struct SegmentTree
{
	int N;
	vector<vector<pair<int, int>>> ST;
	SegmentTree(int n)
	{
		for (N = 1; N < n; N <<= 1){}
		ST = vector<vector<pair<int, int>>>(N << 1);
	}
	void rangePush(int L, int R, pair<int, int> x, int i, int l, int r)
	{
		if (r <= L || R <= l)
			return;

		if (L <= l && r <= R)
		{
			ST[i].push_back(x);
			return;
		}
		int m = (l + r) / 2;
		rangePush(L, R, x, i << 1, l, m);
		rangePush(L, R, x, i << 1 | 1, m, r);
	}
	void rangePush(int L, int R, pair<int, int> x)
	{
		rangePush(L, R, x, 1, 0, N);
	}
	void sortAll()
	{
		for (int i = 1; i < (N << 1); ++i)
			sort(ST[i].begin(), ST[i].end());
	}
	vector<int> pointGet(int p, int v)
	{
		vector<int> ans;
		for (p += N; p; p >>= 1)
		{
			int i = lower_bound(ST[p].begin(), ST[p].end(), make_pair(v, 0)) - ST[p].begin();
			while (i < (int)(ST[p].size()) && ST[p][i].first == v)
				ans.push_back(ST[p][i++].second);
		}
		return ans;
	}
};

int N, D, U;
int H[100000];
SegmentTree ST(100001);

void init(int n, int d, int h[]) {
    N = n;
    D = d;
    for (int i = 0; i < n; i++)
      H[i] = h[i];
}

void curseChanges(int u, int A[], int B[])
{
  U = u;
	map<pair<int, int>, int> mp;
	for (int i = 0; i < U; ++i)
	{
		if (mp[make_pair(A[i], B[i])] > 0)
		{
			ST.rangePush(mp[make_pair(A[i], B[i])], i + 1, make_pair(A[i], B[i]));
			ST.rangePush(mp[make_pair(A[i], B[i])], i + 1, make_pair(B[i], A[i]));
			mp[make_pair(A[i], B[i])] = 0;
		}
		else
			mp[make_pair(A[i], B[i])] = i + 1;
	}
	for (auto e : mp)
		if (e.second)
		{
			ST.rangePush(e.second, U + 1, e.first);
			ST.rangePush(e.second, U + 1, e.first);
		}

	ST.sortAll();
}

int question(int x, int y, int v)
{
	auto X = ST.pointGet(v, x);
	auto Y = ST.pointGet(v, y);
	for (int i = 0; i < (int)(X.size()); ++i)
		X[i] = H[X[i]];

	for (int i = 0; i < (int)(Y.size()); ++i)
		Y[i] = H[Y[i]];

	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	int ans = (int)(1e9);
	for (int i = 0, j = 0; i < (int)(X.size()); ++i)
	{
		while (j < (int)(Y.size()) && X[i] > Y[j])
			++j;

		if (j < (int)(Y.size()))
			ans = min(ans, abs(X[i] - Y[j]));

		if (j)
			ans = min(ans, abs(X[i] - Y[j - 1]));
	}
	return ans;
}

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