#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];
set<ll> ss;
vector<ll> cpr;
ll tmp[2000010];
map<ll, ll> dp[2000010];
vector<pll> pmp[2000010];
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;
int wh(ll x){ return int(lower_bound(cpr.begin(), cpr.end(), x) - cpr.begin());}
void pf(ll x){
if(!x || ss.find(x) != ss.end()) return;
ss.insert(x);
pf((x - 1) / 2);
pf(x / 2);
}
void f(ll x){
if(!x || ss.find(x) != ss.end()) return;
ss.insert(x);
if(x == 1){
dp[wh(1)][1]++;
return;
}
int tt = wh(x);
if((x - 1) / 2){
f((x - 1) / 2);
int t = wh((x - 1) / 2);
for(auto &i : dp[t]) dp[tt][i.first] += i.second;
}
if(x / 2){
f(x / 2);
int t = wh(x / 2);
for(auto &i : dp[t]) dp[tt][i.first] += i.second;
}
dp[tt][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 = ((x - 1) / 2) ? val(wh((x - 1) / 2), cpr[t]) : 0;
if(v == c - 1 && x == cpr[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;
pf(l[i]);
}
while(!ss.empty()){
cpr.push_back(*ss.begin());
ss.erase(ss.begin());
}
for(int i = 0; i <= n; i++){
f(l[i]);
int t = wh(l[i]);
for(auto &j : dp[t]){
int u = wh(j.first);
tmp[u] += j.second;
pmp[u].push_back({i, j.second});
}
}
for(int i = 0; i <= 2000000; i++){
if(!pmp[i].empty()) tr[i] = new Seg(pmp[i]);
pmp[i].clear();
}
int t = 1999999;
ll cs = 0;
for(ll c; q--; ){
scanf("%lld", &c);
if(c <= n){
printf("%lld\n", a[c]);
continue;
}
c -= n;
while(cs + tmp[t] < c){
cs += tmp[t];
t--;
}
c -= cs;
ll u, d; tie(u, d) = tr[t]->get(c);
printf("%lld\n", g(l[u], s[u], t, d));
}
}
Compilation message
ogledala.cpp: In constructor 'Seg::Seg(const std::vector<std::pair<long long int, long long int> >&)':
ogledala.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(sz = 1; sz < v.size(); sz *= 2);
^
ogledala.cpp:21: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:84: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:85: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:112:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &c);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4000 ms |
161404 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
166960 KB |
Output is correct |
| 2 |
Correct |
79 ms |
167496 KB |
Output is correct |
| 3 |
Memory limit exceeded |
2889 ms |
524288 KB |
Memory limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
1729 ms |
524288 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
