// 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;
void clean(vector<pll> &vec)
{
sort(all(vec));
vector<pll> res;
int n = vec.size();
for (int i = 0; i < n;)
{
int j;
ll cnt = 0;
for (j = i; j < n && vec[j].fr == vec[i].fr; j++)
cnt += vec[j].sc;
res.pb({vec[i].fr, cnt});
i = j;
}
vec = res;
}
vector<pll> findsegs(ll n)
{
if (n == 1) return {{1, 1}};
if (n == 2) return {{2, 1}, {1, 1}};
if (n == 4) return {{4, 1}, {2, 1}, {1, 2}};
if (n == 6) return {{6, 1}, {3, 1}, {2, 1}, {1, 3}};
if (n % 2)
{
vector<pll> res = findsegs(n/2);
for (pll &p : res) p.sc *= 2;
res.pb({n, 1});
return res;
}
if (n % 4) // 4k + 2
{
vector<pll> res = findsegs(n/4 - 1);
vector<pll> kres = findsegs(n/4);
for (pll p : kres)
res.pb({p.fr, p.sc * 3});
res.pb({n/2, 1});
res.pb({n/2 - 1, 1});
res.pb({n, 1});
clean(res);
return res;
}
// 4k
vector<pll> res = findsegs(n/4);
vector<pll> k1res = findsegs(n/4 - 1);
for (pll p : k1res)
res.pb({p.fr, p.sc * 3});
res.pb({n/2, 1});
res.pb({n/2 - 1, 1});
res.pb({n, 1});
clean(res);
return res;
}
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 getcnt(ll n, ll k)
{
if (n == k)
return 1;
if (n == 1) return (k == 1 ? 1 : 0);
if (n == 2) return (k <= 2 ? 1 : 0);
if (n == 4) return (k == 1 ? 2 : (k == 2 || k == 4 ? 1 : 0));
if (n == 6) return (k == 1 ? 3 : (k == 2 || k == 3 || k == 6 ? 1 : 0));
if (n % 2)
return getcnt(n/2, k) * 2;
if (k == n/2 || k == (n + 1)/2 - 1)
return 1;
if (n % 4) // 4k + 2
return getcnt(n/4 - 1, k) + getcnt(n/4, k) * 3;
// 4k
return getcnt(n/4, k) + getcnt(n/4 - 1, k) * 3;
}
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);
if (p >= k)
return findmid((n + 1)/2 - 1, l, k, len);
return findmid(n/2, l + (n + 1)/2, k - p, len);
}
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);
for (pll p : vec)
segs.pb({{p.fr, i}, p.sc});
}
}
if (a[n] < m)
{
vector<pll> vec = findsegs(m - a[n]);
for (pll p : vec)
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);
/*
for (auto p : segs)
cout << "((" << p.fr.fr << ", " << p.fr.sc << "), " << p.sc << ")\n";
dbgr(ps.begin(), ps.end());
*/
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 |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
33 ms |
3044 KB |
Output is correct |
| 4 |
Correct |
39 ms |
3300 KB |
Output is correct |
| 5 |
Correct |
82 ms |
9608 KB |
Output is correct |
| 6 |
Correct |
88 ms |
10320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
688 KB |
Output is correct |
| 2 |
Correct |
26 ms |
688 KB |
Output is correct |
| 3 |
Execution timed out |
4062 ms |
25692 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3396 ms |
127892 KB |
Output is correct |
| 2 |
Correct |
3585 ms |
132112 KB |
Output is correct |
| 3 |
Execution timed out |
4094 ms |
50496 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
