Submission #387377

#	Time	Username	Problem	Language	Result	Execution time	Memory
387377		sinamhdv	OGLEDALA (COI15_ogledala)	C++11	100 / 100	3777 ms	234860 KiB

ogledala

// COI15_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

ll m;
int n, q;
ll a[MAXN];
vector<pair<pll, ll>> segs;
vector<ll> ps;

vector<pll> findsegs(ll n, ll x = 1, ll y = 0)	// x * n, y * (n + 1)
{
	if (n == 0) return {{1, y}};

	if (n % 2)
	{
		vector<pll> vec = findsegs(n/2, 2 * x + y, y);
		vec.pb({n, x});
		vec.pb({n + 1, y});
		return vec;
	}
	vector<pll> vec = findsegs(n/2 - 1, x, x + 2 * y);
	vec.pb({n, x});
	vec.pb({n + 1, y});
	return vec;
}

bool cmp(pair<pll, ll> x, pair<pll, ll> y)
{
	if (x.fr.fr == y.fr.fr) return x.fr.sc < y.fr.sc;
	return x.fr.fr > y.fr.fr;
}

ll findmid(ll n, ll l, ll k, ll len)
{
	if (n == 1) return l;
	if (n == 2) return (len == 1 ? l + 1 : l);
	if (n == len)
	{
		ll r = l + n - 1;
		return (r + l) / 2;
	}
	
	//ll p = getcnt((n + 1)/2 - 1, len);
	vector<pll> vec = findsegs((n + 1)/2 - 1);
	ll p = 0;
	for (pll pr : vec) if (pr.fr == len) p += pr.sc;

	if (p >= k)
		return findmid((n + 1)/2 - 1, l, k, len);
	return findmid(n/2, l + (n + 1)/2, k - p, len);
}

void clean(vector<pll> &vec)
{
	vector<pll> res;
	sort(all(vec));
	while (vec.size())
	{
		res.pb(vec.back());
		vec.pop_back();
		int s = res.size();
		if (s >= 2 && res[s - 1].fr == res[s - 2].fr)
			res[s - 2].sc += res[s - 1].sc, res.pop_back();
	}
	vec = res;
}

int32_t main(void)
{
	fast_io;
	cin >> m >> n >> q;
	FOR(i, 1, n + 1)
	{
		cin >> a[i];
		if (a[i] > a[i - 1] + 1)
		{
			vector<pll> vec = findsegs(a[i] - a[i - 1] - 1);
			clean(vec);
			for (pll p : vec) if (p.sc)
				segs.pb({{p.fr, i}, p.sc});
		}
	}
	if (a[n] < m)
	{
		vector<pll> vec = findsegs(m - a[n]);
		clean(vec);
		for (pll p : vec) if (p.sc)
			segs.pb({{p.fr, n + 1}, p.sc});
	}
	a[n + 1] = m + 1;

	sort(all(segs), cmp);
	ps.pb(0);
	for (auto p : segs)
		ps.pb(ps.back() + p.sc);

	while (q--)
	{
		ll x;
		cin >> x;
		if (x <= n)
		{
			cout << a[x] << endl;
			continue;
		}
		x -= n;
		int pos = lower_bound(all(ps), x) - ps.begin();
		ll ord = x - ps[pos - 1];
		auto p = segs[pos - 1];
		ll mainlen = a[p.fr.sc] - a[p.fr.sc - 1] - 1;
		ll len = p.fr.fr;

		cout << findmid(mainlen, a[p.fr.sc - 1] + 1, ord, len) << endl;
	}

	return 0;
}

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