#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int n, q;
ll m, a[100010], l[200010], s[100010];
map<ll, ll> tmp;
map<ll, vector<pll>> pmp;
map<ll, map<ll, ll>> dp;
struct Seg{
int sz;
ll *p, *dat;
Seg(const vector<pll> &v){
for(sz = 1; sz < v.size(); sz *= 2);
p = new ll[int(v.size())];
dat = new ll[2 * sz];
for(int i = 0; i < v.size(); i++){
p[i] = v[i].first;
dat[i + sz] = v[i].second;
}
fill(dat + sz + int(v.size()), dat + 2 * sz, 0);
for(int i = sz - 1; i >= 1; i--){
dat[i] = dat[2 * i] + dat[2 * i + 1];
}
}
pll get(ll v){
int x = 1;
while(x < sz){
if(dat[2 * x] < v){
v -= dat[2 * x];
x = 2 * x + 1;
}
else x = 2 * x;
}
return {p[x - sz], v};
}
};
map<ll, Seg*> tr;
void f(ll x){
if(!x || dp.find(x) != dp.end()) return;
if(x == 1){
dp[1][1]++;
return;
}
if((x - 1) / 2){
f((x - 1) / 2);
for(auto &i : dp[(x - 1) / 2]) dp[x][i.first] += i.second;
}
if(x / 2){
f(x / 2);
for(auto &i : dp[x / 2]) dp[x][i.first] += i.second;
}
dp[x][x]++;
}
ll val(ll x, ll y){ return (dp[x].find(y) == dp[x].end()) ? 0 : dp[x][y]; }
ll g(ll x, ll s, ll t, ll c){
ll v = val((x - 1) / 2, t);
if(v == c - 1 && x == t) return s + (x - 1) / 2;
if(v >= c) return g((x - 1) / 2, s, t, c);
return g(x / 2, s + (x + 1) / 2, t, c - v);
}
int main(){
scanf("%lld%d%d", &m, &n, &q);
for(int i = 1; i <= n; i++) scanf("%lld", a + i);
a[n + 1] = m + 1;
for(int i = 0; i <= n; i++){
l[i] = a[i + 1] - a[i] - 1;
s[i] = a[i] + 1;
f(l[i]);
for(auto &j : dp[l[i]]){
tmp[j.first] += j.second;
pmp[j.first].push_back({i, j.second});
}
}
for(auto &i : pmp){
tr[i.first] = new Seg(i.second);
}
auto t = tmp.end(); t--;
ll cs = 0;
for(ll c; q--; ){
scanf("%lld", &c);
if(c <= n){
printf("%lld\n", a[c]);
continue;
}
c -= n;
while(cs + t->second < c){
cs += t->second;
t--;
}
c -= cs;
ll u, d; tie(u, d) = tr[t->first]->get(c);
printf("%lld\n", g(l[u], s[u], t->first, d));
}
}
Compilation message
ogledala.cpp: In constructor 'Seg::Seg(const std::vector<std::pair<long long int, long long int> >&)':
ogledala.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(sz = 1; sz < v.size(); sz *= 2);
^
ogledala.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); i++){
^
ogledala.cpp: In function 'int main()':
ogledala.cpp:69:31: 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:70:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n; i++) scanf("%lld", a + i);
^
ogledala.cpp:87:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &c);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
5156 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5156 KB |
Output is correct |
| 3 |
Correct |
33 ms |
7236 KB |
Output is correct |
| 4 |
Correct |
26 ms |
7340 KB |
Output is correct |
| 5 |
Correct |
69 ms |
13652 KB |
Output is correct |
| 6 |
Correct |
53 ms |
14484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
43 ms |
11228 KB |
Output is correct |
| 2 |
Correct |
49 ms |
11756 KB |
Output is correct |
| 3 |
Memory limit exceeded |
2816 ms |
524288 KB |
Memory limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4000 ms |
460212 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
