Submission #619563

#	Time	Username	Problem	Language	Result	Execution time	Memory
619563		Drew_	OGLEDALA (COI15_ogledala)	C++17	0 / 100	4072 ms	273796 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});
	
	vector<ll> zip; 
	for (auto &[l, p] : len)
	{
		set<ll, greater<ll>> st;
		st.insert(l);

		while (!st.empty())
		{
			ll x = *st.begin(); st.erase(st.begin());
			
			zip.pb(x);			
			if (x >> 1) st.insert(x >> 1);
			if ((x-1) >> 1) st.insert((x-1) >> 1);
		}
	}
	sort(zip.begin(), zip.end());
	zip.resize(unique(zip.begin(), zip.end()) - zip.begin());

	// cerr << "zip: ";
	// for (int x : zip)
	// 	cerr << x << ", ";
	// cerr << '\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: 0 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59