제출 #335196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335196		guka415	OGLEDALA (COI15_ogledala)	C++14	41 / 100	89 ms	16600 KiB

ogledala

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (long long i = k; i < n; i++)
#define ford(i, k, n) for (long long i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <set>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

const int sz = 5e5;
ll n, m, q;
ll p[sz], qu[sz], ans[sz];

int main() {
	fast;
	cin >> m >> n >> q;
	priority_queue<pii,vector<pii>, greater<pii>> pq;
	foru(i, 0, n) {
		cin >> p[i];
		ans[i + 1] = p[i];
		if (i == 0) {
			if (p[i] != 1)pq.push({ -(p[i] - 1),1 });
		}
		if (i == n - 1) {
			if (p[i] != m)pq.push({ -(m - p[i]),p[i]+1 });
		}
		if (i!=0 && p[i]-p[i-1]>1){
			pq.push({ -(p[i] - p[i - 1] - 1),p[i - 1] + 1 });
		}
	}
	for (int i = n + 1; i <= min(m, (ll)3e5+5) && !pq.empty(); i++) {
		pii top = pq.top(); pq.pop();
		ll len = -top.first, l = top.second, place = l + (len - 1) / 2;
		ans[i] = place;
		ll llen = (len - 1) / 2, rlen = len / 2;
		if (llen != 0) {
			pq.push({ -llen,l });
		}
		if (rlen != 0)pq.push({ -rlen,l + llen + 1 });
	}
	while (q--) {
		ll rr;
		cin >> rr;
		cout << ans[rr] << '\n';
	}
	return 0;
}

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