oj.uz

답안 #387377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387377 2021-04-08T10:11:36 Z sinamhdv OGLEDALA (COI15_ogledala) C++11
100 / 100
 3777 ms 234860 KB 
// 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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 53 ms 3044 KB Output is correct
4 Correct 48 ms 3300 KB Output is correct
5 Correct 94 ms 9556 KB Output is correct
6 Correct 117 ms 10452 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 684 KB Output is correct
2 Correct 34 ms 684 KB Output is correct
3 Correct 1816 ms 215968 KB Output is correct
4 Correct 1816 ms 219260 KB Output is correct
5 Correct 2025 ms 231752 KB Output is correct
6 Correct 2036 ms 234840 KB Output is correct

Subtask #3
59.0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1637 ms 127976 KB Output is correct
2 Correct 1640 ms 132236 KB Output is correct
3 Correct 2654 ms 200272 KB Output is correct
4 Correct 2572 ms 203496 KB Output is correct
5 Correct 3777 ms 231736 KB Output is correct
6 Correct 3679 ms 234860 KB Output is correct