Submission #1323703

#TimeUsernameProblemLanguageResultExecution timeMemory
1323703NikoBaoticOGLEDALA (COI15_ogledala)C++20
19 / 100
89 ms20544 KiB
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define F first
#define S second
#define	pb push_back
#define	sz(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 10;

int m, n, q;

set<pii> o;

ll run() {
	ll vel = prev(o.end())->F;
	ll ind = -prev(o.end())->S;

	o.erase(prev(o.end()));

	ll cur = ind + (vel - 1) / 2;

	o.insert({(vel - 1) / 2, -ind});
	o.insert({vel / 2, -(cur + 1)});

	return cur;
}

ll a[N];

int main() {
	FIO;

	cin >> m >> n >> q;

	ll last = 0;

	for (int i = 0; i < n; i++) {
		ll t;
		cin >> t;

		a[i] = t;

		o.insert({t - last - 1, -(last + 1)});

		last = t;
	}
	
	o.insert({m + 1 - last - 1, -(last + 1)});

	int br = n;

	for (int i = 0; i < q; i++) {
		ll t;
		cin >> t;

		ll ans = 0;

		if (t <= n) ans = a[t - 1];

		while (br < t) {
			ans = run();
			br++;
		}

		cout << ans << '\n';
	}

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...