#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
const int MAXN = 1e5 + 5;
struct state {
ll len, cnt;
int pos;
inline bool operator <(const state &rhs) const {
if (len == rhs.len)
return pos < rhs.pos;
return len > rhs.len;
}
};
vector<pair<ll, ll> > vec;
void comp(ll x) {
vec.clear();
if (x == 0) return;
vec.pb({x + 1, 0});
vec.pb({x, 1});
for (int i = 0; i < (int)vec.size(); i += 2) {
ll len_fi = vec[i].fi / 2, cnt_fi = vec[i].se;
ll len_se = (vec[i + 1].fi - 1) / 2, cnt_se = vec[i + 1].se;
if (len_fi == 0 && len_se == 0) break;
if ((vec[i].fi - 1) / 2 == len_fi)
cnt_fi += vec[i].se;
else
cnt_se += vec[i].se;
if (vec[i + 1].fi / 2 == len_fi)
cnt_fi += vec[i + 1].se;
else
cnt_se += vec[i + 1].se;
vec.pb({len_fi, cnt_fi});
vec.pb({len_se, cnt_se});
}
while (!vec.empty() && vec.back().fi == 0) vec.pop_back();
ll one = 0;
while (!vec.empty() && vec.back().fi == 1) {
one += vec.back().se; vec.pop_back();
}
if (one > 0) vec.pb({1, one});
}
vector<state> seg;
vector<ll> pref;
void solve(ll x, int pos) {
comp(x);
for (auto it : vec)
seg.pb((state){it.fi, it.se, pos});
}
//map<pair<ll, ll>, ll> memo;
ll freq(ll len, ll want) {
comp(len);
ll res = 0;
for (auto it : vec)
if (it.fi == want)
res += it.se;
return res;
/*if (len < want) return 0;
if (len == want) return 1;
ll L = (len - 1) / 2, R = len / 2;
if (L == R) return 2LL * freq(L, want);
return freq(L, want) + freq(R, want);
//if (memo.count(mp(len, want)))
// return memo[mp(len, want)];
//return memo[mp(len, want)] = freq((len - 1) / 2, want) + freq(len / 2, want);
*/
}
ll getans(ll len, ll want, ll k) {
//printf("ans for (%lld, %lld, %lld):", len, want, k);
ll ret = 0;
while (len > want) {
ll L = (len - 1) / 2;
ll R = len / 2;
ll cur = freq(L, want);
//printf("%lld contains %lld of type %lld\n", L, cur, want);
if (cur >= k) {
len = L;
} else {
len = R;
k -= cur;
ret += L + 1;
}
}
ret += (want + 1) / 2;
//printf(" %lld\n", ret);
return ret;
}
ll a[MAXN];
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
ll m;
int n, q;
scanf("%lld %d %d", &m, &n, &q);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
a[0] = 0;
a[n + 1] = m + 1;
for (int i = 0; i <= n; i++) {
if (a[i + 1] - a[i] - 1 > 0)
solve(a[i + 1] - a[i] - 1, i);
}
sort(all(seg));
int sz = (int)seg.size();
//for (auto it : seg)
// printf("(%lld, %lld, %lld)\n", it.len, it.cnt, it.pos);
pref.resize(sz);
pref[0] = seg[0].cnt;
for (int i = 1; i < sz; i++)
pref[i] = pref[i - 1] + seg[i].cnt;
int k = 0;
while (q--) {
ll x;
scanf("%lld", &x);
if (x <= n)
printf("%lld\n", a[x]);
else {
x -= n;
while (k < sz - 1 && pref[k] < x) k++;
int pos = seg[k].pos;
printf("%lld\n", a[pos] + getans( a[pos + 1] - a[pos] - 1, seg[k].len, x - (k == 0 ? 0 : pref[k - 1]) ) );
}
}
return 0;
}
Compilation message
ogledala.cpp: In function 'int main()':
ogledala.cpp:157:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %d %d", &m, &n, &q);
^
ogledala.cpp:159:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &a[i]);
^
ogledala.cpp:181:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2804 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2804 KB |
Output is correct |
| 3 |
Correct |
46 ms |
5192 KB |
Output is correct |
| 4 |
Correct |
46 ms |
5192 KB |
Output is correct |
| 5 |
Correct |
86 ms |
12104 KB |
Output is correct |
| 6 |
Correct |
113 ms |
21320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
3172 KB |
Output is correct |
| 2 |
Correct |
16 ms |
3172 KB |
Output is correct |
| 3 |
Correct |
1033 ms |
297804 KB |
Output is correct |
| 4 |
Correct |
993 ms |
297804 KB |
Output is correct |
| 5 |
Correct |
1119 ms |
297804 KB |
Output is correct |
| 6 |
Correct |
1149 ms |
297804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
943 ms |
150348 KB |
Output is correct |
| 2 |
Correct |
1006 ms |
150348 KB |
Output is correct |
| 3 |
Correct |
1506 ms |
297804 KB |
Output is correct |
| 4 |
Correct |
1546 ms |
297804 KB |
Output is correct |
| 5 |
Correct |
2119 ms |
297804 KB |
Output is correct |
| 6 |
Correct |
2176 ms |
297804 KB |
Output is correct |
