#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 300005;
ll l, n, m, a[N], qry[N], cur[N];
vector<vector<ll> > dt[N];
vector<ll> v[N];
priority_queue<pll> pq;
void add (vector<ll> &V, ll A) {
if(A <= 0) return;
for(auto &T : V) if(T == A) return;
V.push_back(A);
}
void upd (vector<ll> &D, ll I, ll A) {
while(D.size() <= I) D.push_back(0);
D[I] += A;
}
ll geti (vector<ll> &V, ll I, ll P) {
for(ll i=0;i<I;i++) if(V[i] == P) return i;
return -1;
}
void prev (vector<vector<ll> > &D, vector<ll> &V, ll I, ll A) {
ll P = geti(V, I, A);
if(P == -1) return;
for(ll i=0;i<D[P].size();i++) upd(D[I], i, D[P][i]);
}
void kth (ll I, ll C, ll O, ll S, ll E, ll K) {
if(C == O) {printf("%lld\n",(S+E)/2); return;}
ll L = E-S+1, I1 = geti(v[I], C, (L-1)/2), I2 = geti(v[I], C, L/2);
if(I1 >= O && dt[I][I1][O] >= K) kth(I, I1, O, S, (S+E)/2-1, K);
else kth(I, I2, O, (S+E)/2+1, E, K-(I1>=O?dt[I][I1][O]:0));
}
int main() {
scanf("%lld%lld%lld",&l,&n,&m);
for(ll i=1;i<=n;i++) {
scanf("%lld",&a[i]);
}
a[n+1] = l+1;
for(ll i=1;i<=n+1;i++) {
add(v[i], a[i]-a[i-1]-1);
for(ll j=0;j<v[i].size();j++) {
add(v[i], v[i][j]/2);
add(v[i], (v[i][j]-1)/2);
}
reverse(v[i].begin(), v[i].end());
for(ll j=0;j<v[i].size();j++) {
dt[i].push_back(vector<ll>());
prev(dt[i], v[i], j, v[i][j]/2);
prev(dt[i], v[i], j, (v[i][j]-1)/2);
upd(dt[i][j], j, 1);
}
}
for(ll i=1;i<=n+1;i++) {
cur[i] = v[i].size();
if(--cur[i] >= 0) pq.push({v[i][cur[i]], -i});
}
ll cq = 1, dn = n;
for(ll i=1;i<=m;i++) {
scanf("%lld",&qry[i]);
if(qry[i] <= n) {
cq++;
printf("%lld\n",a[qry[i]]);
}
}
while(!pq.empty()) {
ll C = -pq.top().second; pq.pop();
ll V = dt[C][v[C].size()-1][cur[C]];
for(;cq <= m && qry[cq] <= dn + V; cq++) {
kth(C, v[C].size()-1, cur[C], a[C-1]+1, a[C]-1, qry[cq]-dn);
}
if(cq > m) break;
dn += V;
if(--cur[C] >= 0) pq.push({v[C][cur[C]], -C});
}
}
Compilation message
ogledala.cpp: In function 'void upd(std::vector<long long int>&, ll, ll)':
ogledala.cpp:20:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(D.size() <= I) D.push_back(0);
^
ogledala.cpp: In function 'void prev(std::vector<std::vector<long long int> >&, std::vector<long long int>&, ll, ll)':
ogledala.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=0;i<D[P].size();i++) upd(D[I], i, D[P][i]);
^
ogledala.cpp: In function 'int main()':
ogledala.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<v[i].size();j++) {
^
ogledala.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<v[i].size();j++) {
^
ogledala.cpp:43:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&l,&n,&m);
^
ogledala.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
^
ogledala.cpp:68:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&qry[i]);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
23116 KB |
Output is correct |
| 2 |
Correct |
3 ms |
23116 KB |
Output is correct |
| 3 |
Correct |
46 ms |
26952 KB |
Output is correct |
| 4 |
Correct |
49 ms |
27476 KB |
Output is correct |
| 5 |
Correct |
136 ms |
38328 KB |
Output is correct |
| 6 |
Correct |
136 ms |
39992 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
24436 KB |
Output is correct |
| 2 |
Correct |
16 ms |
24568 KB |
Output is correct |
| 3 |
Memory limit exceeded |
1316 ms |
524288 KB |
Memory limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Memory limit exceeded |
1439 ms |
524288 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
