Submission #619274

#	Time	Username	Problem	Language	Result	Execution time	Memory
619274		Drew_	OGLEDALA (COI15_ogledala)	C++17	19 / 100	2740 ms	524288 KiB

ogledala

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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define size(x) (int)x.size()

using ii = pair<int, int>;
using ll = long long;
using pl = pair<ll, ll>;

const int MAX = 1e5 + 69;
const ll inf = 1e18 + 69;

ll M, N, Q;
ll A[MAX], B[MAX], Blen[MAX], Bpos[MAX], Bblank[MAX];
ll ans[MAX];

int32_t main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> M >> N >> Q;
	for (int i = 1; i <= N; ++i)
		cin >> A[i];

	int si = 1;
	for (int i = 1; i <= Q; ++i)
	{
		cin >> B[i];
		if (B[i] <= N)
			ans[i] = A[B[i]], si++;
		B[i] -= N;
	}
	A[0] = 0; A[N+1] = M+1;

	vector<pl> len;
	for (int i = 0; i <= N; ++i) if (A[i+1] - A[i] - 1)
		len.pb({A[i+1] - A[i] - 1, A[i] + 1});

	map<ll, ll> fq;
	vector<ll> zip;
	{
		priority_queue<ll> pq;
		for (auto [l, x] : len)
		{
			if (!fq.count(l))
				pq.push(l);
			fq[l]++;
		}

		const auto genfq = [&]()
		{
			while (!pq.empty())
			{
				ll val = pq.top(); pq.pop();
			
				if ((val-1) >> 1)
				{
					if (!fq.count((val-1) >> 1))
						pq.push((val-1) >> 1);
					fq[(val-1) >> 1] += fq[val];
				}
				if (val >> 1)
				{
					if (!fq.count(val >> 1))
						pq.push(val >> 1);
					fq[val >> 1] += fq[val];
				}
			}
		};
		genfq();
		for (const auto &[x, y] : fq)
			zip.pb(x);
	}


	// cerr << "zip: ";
	// for (int x : zip)
	// 	cerr << x << ", ";
	// cerr << '\n';

	vector<ii> nxt(size(zip)); // division by 2
	for (int a = 0; a < size(zip); ++a)
	{
		ll L = (zip[a]-1) >> 1, R = (zip[a]) >> 1;
		int i = -1, j = -1;
		if (L > 0) i = (int)(lower_bound(zip.begin(), zip.end(), L) - zip.begin());
		if (R > 0) j = (int)(lower_bound(zip.begin(), zip.end(), R) - zip.begin());
		nxt[a] = { i, j };
	}

	vector<vector<int>> impt(size(zip));
	for (int i = 0; i < size(zip); ++i)
	{
		impt[i].pb(i);
		if (nxt[i].f1 != -1) for (int x : impt[nxt[i].f1])
			impt[i].pb(x);
		if (nxt[i].s2 != -1) for (int x : impt[nxt[i].s2])
			impt[i].pb(x);
		sort(impt[i].begin(), impt[i].end());
		impt[i].resize(unique(impt[i].begin(), impt[i].end()) - impt[i].begin());
	}

	vector<ll> freq(size(zip));	
	{
		vector<ll> ctr(size(zip));
		vector<queue<pl>> memo(size(zip));
		{
			vector<pl> vec(fq.rbegin(), fq.rend());
			for (int i = 0; i < size(vec); ++i)
				vec[i].f1 = (int)(lower_bound(zip.begin(), zip.end(), vec[i].f1) - zip.begin());
			for (int i = 1; i < size(vec); ++i)
				vec[i].s2 += vec[i-1].s2;

			for (int i = si, j = 0; i <= Q; ++i)
			{
				while (vec[j].s2 < B[i])
					++j;
				Blen[i] = vec[j].f1;
				Bpos[i] = B[i] - (j ? vec[j-1].s2 : 0);
			
				memo[Blen[i]].push({Bpos[i], i});
			}
		}
		fq.clear();

		for (int i = 0; i < size(len); ++i)
		{
			auto [l, x] = len[i];

			int id = (int)(lower_bound(zip.begin(), zip.end(), l) - zip.begin());
			for (int j : impt[id])
				freq[j] = 0;
			freq[id] = 1;

			for (int j = size(impt[id]) - 1; j >= 0; --j)
			{
				auto [a, b] = nxt[impt[id][j]];
				if (a != -1)
					freq[a] += freq[impt[id][j]];
				if (b != -1)
					freq[b] += freq[impt[id][j]];
			}

			vector<pl> vec;
			for (int j = size(impt[id]) - 1; j >= 0; --j)
				vec.pb({impt[id][j], freq[impt[id][j]]});

			// there are ~(log MAX) values
			for (auto [x, y] : vec)
			{
				ctr[x] += y;
				while (!memo[x].empty() && memo[x].front().f1 <= ctr[x])
				{
					Bpos[memo[x].front().s2] -= ctr[x] - y;
					Bblank[memo[x].front().s2] = i;
					memo[x].pop();
				}
			}
		}
	}

	for (auto &i : freq)
		i = 0;

	for (int i = si; i <= Q; ++i)
	{
		auto [val, pos] = len[Bblank[i]];
		int id = (lower_bound(zip.begin(), zip.end(), val) - zip.begin());
		// cerr << "\n\n solving: " << i << " " << Blen[i] << " " << Bpos[i] << '\n';
		for (;;)
		{
			// cerr << "id: " << id << " " << pos << '\n';
			if (id == Blen[i])
			{
				ans[i] = pos + (zip[id]-1) / 2;
				break;
			}

			// check to go to left or right
			ll L = nxt[id].f1, R = nxt[id].s2;

			if (L == -1)
			{
				id = R, pos++;
				continue;
			}

			freq[L] = 1;
			for (int j = size(impt[L]) - 1; j >= 0; --j)
			{
				if (impt[L][j] < Blen[i])
					break;

				auto [a, b] = nxt[impt[L][j]];
				if (a >= Blen[i])
					freq[a] += freq[impt[L][j]];
				if (b >= Blen[i])
					freq[b] += freq[impt[L][j]];
			}

			// cerr << "freq: ";
			// for (int i = 0; i < size(zip); ++i)
			// 	cerr << freq[i] << ", ";
			// cerr << '\n';
			// cerr << Bpos[i] << " and " << freq[Blen[i]] << '\n';

			if (Bpos[i] <= freq[Blen[i]]) id = L;
			else id = R, pos += zip[L] + 1, Bpos[i] -= freq[Blen[i]];
		
			for (int j : impt[L])
				freq[j] = 0;
		}
	}

	for (int i = 1; i <= Q; ++i)
		cout << ans[i] << '\n';

	return 0;
}	

• Subtask 1: 19 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59