// 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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
