제출 #387270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387270		sinamhdv	OGLEDALA (COI15_ogledala)	C++11	41 / 100	201 ms	44268 KiB

ogledala

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100
#define MAXB 300100

ll m;
int n, q;
ll a[MAXB];

int32_t main(void)
{
	fast_io;
	cin >> m >> n >> q;

	FOR(i, 1, n + 1)
		cin >> a[i];
	
	set<pair<ll, pll>> s;

	if (a[1] > 1)
		s.insert({a[1] - 1, {-1, a[1] - 1}});
	if (a[n] < m)
		s.insert({m - a[n], {-(a[n] + 1), m}});

	FOR(i, 2, n + 1)
	{
		if (a[i] == a[i - 1] + 1)
			continue;
		s.insert({a[i] - a[i - 1] - 1, {-(a[i - 1] + 1), a[i] - 1}});
	}

	FOR(i, n + 1, min((ll)MAXB, m + 1))
	{
		pll p = s.rbegin() -> sc;
		auto it = s.end();
		it--;
		s.erase(it);

		p.fr = -p.fr;

		a[i] = (p.fr + p.sc) / 2;
		
		if (a[i] != p.fr)
			s.insert({a[i] - p.fr, {-p.fr, a[i] - 1}});
		
		if (a[i] != p.sc)
			s.insert({p.sc - a[i], {-(a[i] + 1), p.sc}});
	}

	while (q--)
	{
		int b;
		cin >> b;
		cout << a[b] << endl;
	}

	return 0;
}

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