#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<state> seg;
vector<ll> pref;
void solve(ll x, int pos) {
map<ll, ll> val;
queue<ll> Q;
Q.push(x);
val[x] = 1;
while (!Q.empty()) {
ll u = Q.front();
Q.pop();
vector<ll> gr = {(u - 1) / 2, u / 2};
for (auto v : gr) {
if (!val.count(v)) {
Q.push(v);
}
val[v] += val[u];
}
}
for (auto it : val)
if (it.fi != 0)
seg.pb((state){it.fi, it.se, pos});
}
//map<pair<ll, ll>, ll> memo;
ll freq(ll len, ll want) {
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:132: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:134:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &a[i]);
^
ogledala.cpp:156:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &x);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2812 KB |
Output is correct |
2 |
Correct |
0 ms |
2812 KB |
Output is correct |
3 |
Correct |
63 ms |
5200 KB |
Output is correct |
4 |
Correct |
36 ms |
5200 KB |
Output is correct |
5 |
Correct |
99 ms |
12112 KB |
Output is correct |
6 |
Correct |
139 ms |
12112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
3184 KB |
Output is correct |
2 |
Correct |
6 ms |
3184 KB |
Output is correct |
3 |
Correct |
1899 ms |
297808 KB |
Output is correct |
4 |
Correct |
1879 ms |
297808 KB |
Output is correct |
5 |
Correct |
1899 ms |
297808 KB |
Output is correct |
6 |
Correct |
2073 ms |
297808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2386 ms |
150352 KB |
Output is correct |
2 |
Correct |
2139 ms |
150352 KB |
Output is correct |
3 |
Execution timed out |
4000 ms |
297808 KB |
Execution timed out |
4 |
Halted |
0 ms |
0 KB |
- |