Submission #619019

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

ogledala

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

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

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];

int 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;
	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();

	map<ll, ll> ctr;
	map<ll, queue<pl>> memo;
	{
		vector<pl> vec(fq.rbegin(), fq.rend());
		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});
		}
	}

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

		fq.clear();
		pq.push(l); fq[l]++;

		genfq();
		vector<pl> vec(fq.rbegin(), fq.rend());

		// 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 (int i = si; i <= Q; ++i)
	{
		auto [val, pos] = len[Bblank[i]];
		
		for (;;)
		{
			if (val == Blen[i])
			{
				ans[i] = pos + (val-1) / 2;
				break;
			}

			// check to go to left or right
			ll L = (val - 1) >> 1, R = (val) >> 1;
			
			fq.clear();
			fq[L] = 1; pq.push(L);

			while (!pq.empty())
			{
				ll val = pq.top(); pq.pop();
			
				if (((val-1) >> 1) >= Blen[i])
				{
					if (!fq.count((val-1) >> 1))
						pq.push((val-1) >> 1);
					fq[(val-1) >> 1] += fq[val];
				}
				if ((val >> 1) >= Blen[i])
				{
					if (!fq.count(val >> 1))
						pq.push(val >> 1);
					fq[val >> 1] += fq[val];
				}
			}

			cerr << fq[Blen[i]] << " and " << Bpos[i] << '\n';
			if (Bpos[i] <= fq[Blen[i]]) val = L;
			else val = R, pos += L+1, Bpos[i] -= fq[Blen[i]];
		}
	}

	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