Submission #620212

#	Time	Username	Problem	Language	Result	Execution time	Memory
620212		Drew_	OGLEDALA (COI15_ogledala)	C++17	100 / 100	3448 ms	204916 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];
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});
	
	const auto gen = [&](ll val, ll bound = 1) -> vector<pl>
	{
		vector<pl> res;
		queue<pl> q;

		q.push({val, 1});
		while (!q.empty())
		{
			auto [x, fq] = q.front(); q.pop();
			while (!q.empty() && q.front().f1 == x)
				fq += q.front().s2, q.pop();

			res.pb({x, fq});
			if ((x >> 1) >= bound) q.push({x >> 1, fq});
			if (((x-1) >> 1) >= bound) q.push({(x-1) >> 1, fq});
		}

		return res;
	};

	vector<array<ll, 3>> all;
	for (int i = 0; i < size(len); ++i)
	{
		vector<pl> v = gen(len[i].f1);
		for (auto [x, fq] : v)
			all.pb({x, fq, i});
	}
	sort(all.begin(), all.end(), [](array<ll, 3> &x, array<ll, 3> &y){
		return x[0] > y[0] || (x[0] == y[0] && x[2] < y[2]);
	});

	ll sum = 0;
	for (int i = si, j = 0; i <= Q; ++i)
	{
		while (sum < B[i])
			sum += all[j++][1];

		auto [val, fq, src] = all[j-1];
		B[i] -= sum - fq;
		for (auto [cur, pos] = len[src];;)
		{
			if (val == cur)
			{
				ans[i] = pos + ((val - 1) >> 1);
				break;
			} 

			// check to go to left or right
			ll L = (cur-1) >> 1, R = (cur) >> 1;
			if (L < val)
			{
				cur = R, pos += L+1;
				continue;
			}

			vector<pl> v = gen(L, val);
			if (v.back().f1 != val) cur = R, pos += L+1; 
			else if (B[i] <= v.back().s2) cur = L;
			else cur = R, pos += L+1, B[i] -= v.back().s2;
		}
	}

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

	// vector<ii> nxt(size(zip), mp(-1, -1));
	// for (int x = 0; x < size(zip); ++x)
	// {
	// 	if (((zip[x] - 1) >> 1) > 0)
	// 		nxt[x].f1 = (int)(lower_bound(zip.begin(), zip.end(), (zip[x] - 1) >> 1) - zip.begin());
	// 	if ((zip[x] >> 1) > 0)
	// 		nxt[x].s2 = (int)(lower_bound(zip.begin(), zip.end(), zip[x] >> 1) -  zip.begin());
	// }

	// vector<ll> freq(size(zip), 0);
	// vector<ll> ctr(size(zip));
	// vector<queue<pl>> memo(size(zip));

	// {
	// 	set<int, greater<int>> st;
	// 	for (auto &[l, p] : len)
	// 	{
	// 		int id = (int)(lower_bound(zip.begin(), zip.end(), l) - zip.begin());
	// 		freq[id]++;
	// 		st.insert(id);
	// 	}

	// 	while (!st.empty())
	// 	{
	// 		int x = *st.begin(); st.erase(st.begin());
	// 		if (nxt[x].f1 != -1) freq[nxt[x].f1] += freq[x], st.insert(nxt[x].f1);
	// 		if (nxt[x].s2 != -1) freq[nxt[x].s2] += freq[x], st.insert(nxt[x].s2);
	// 	}
	// }

	// {
	// 	vector<pair<int, ll>> vec;
	// 	for (int i = 0; i < size(zip); ++i)
	// 		vec.pb({i, freq[i]});
	// 	reverse(vec.begin(), vec.end());

	// 	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, p] = len[i];

	// 	int id = (int)(lower_bound(zip.begin(), zip.end(), l) - zip.begin());

	// 	set<int, greater<int>> st; st.insert(id);
	// 	while (!st.empty())
	// 	{
	// 		int x = *st.begin(); st.erase(st.begin());
	// 		freq[x] = 0;
	// 		if (nxt[x].f1 != -1) st.insert(nxt[x].f1);
	// 		if (nxt[x].s2 != -1) st.insert(nxt[x].s2);
	// 	}

	// 	st.insert(id); freq[id] = 1;
	// 	vector<pl> vec;
	// 	while (!st.empty())
	// 	{
	// 		int x = *st.begin(); st.erase(st.begin());
	// 		vec.pb({x, freq[x]});
	// 		if (nxt[x].f1 != -1) freq[nxt[x].f1] += freq[x], st.insert(nxt[x].f1);
	// 		if (nxt[x].s2 != -1) freq[nxt[x].s2] += freq[x], st.insert(nxt[x].s2);
	// 	}

	// 	// 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();
	// 		}
	// 	}
	// }
 
	// fill(freq.begin(), freq.end(), 0);
	// for (int i = si; i <= Q; ++i)
	// {
	// 	auto [val, pos] = len[Bblank[i]];
	// 	int id = (int)(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
	// 		int L = nxt[id].f1, R = nxt[id].s2;

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

	// 		set<int, greater<int>> st; st.insert(L);
	// 		while (!st.empty())
	// 		{
	// 			int x = *st.begin(); st.erase(st.begin());
	// 			freq[x] = 0;
	// 			if (nxt[x].f1 != -1) st.insert(nxt[x].f1);
	// 			if (nxt[x].s2 != -1) st.insert(nxt[x].s2);
	// 		}

	// 		st.insert(L); freq[L] = 1;
	// 		vector<pl> vec;
	// 		while (!st.empty())
	// 		{
	// 			int x = *st.begin(); st.erase(st.begin());
	// 			vec.pb({x, freq[x]});
	// 			if (nxt[x].f1 != -1) freq[nxt[x].f1] += freq[x], st.insert(nxt[x].f1);
	// 			if (nxt[x].s2 != -1) freq[nxt[x].s2] += freq[x], st.insert(nxt[x].s2);
	// 		}
 
	// 		// cerr << "freq: ";
	// 		// for (int zz = 0; zz < size(zip); ++zz)
	// 		// 	cerr << freq[zz] << ", ";
	// 		// cerr << '\n';
	// 		// cerr << Bpos[i] << " and " << freq[Blen[i]] << '\n';
 
	// 		// cerr << i << " -> " << Bpos[i] << " " << freq[Blen[i]] << " AKWOAK\n";

	// 		if (Bpos[i] <= freq[Blen[i]]) id = L;
	// 		else id = R, pos += zip[L] + 1, Bpos[i] -= freq[Blen[i]];
	// 	}
	// }
 
	// for (int i = 1; i <= Q; ++i)
	// 	cout << ans[i] << '\n';
 
	return 0;
}	

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