#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 100005;
ll l, a[N], qry[N], _S, _E, _K;
int n, m, cur[N], _I, _C, _O;
vector<ll> v[N], dt[N];
priority_queue<pair<ll, int> > pq;
int geti (vector<ll> &V, int I, ll P) {
for(int i=max(0,I-3);i<I;i++) if(V[i] == P) return i;
return -1;
}
void add (vector<ll> &V, ll A) {
if(A <= 0 || geti(V, V.size(), A) != -1) return;
V.push_back(A);
}
void kth () {
if(_C == _O) {printf("%lld\n",(_S+_E)/2); return;}
ll L = _E-_S+1;
int I1 = geti(v[_I], _C, (L-1)/2), I2 = (L/2 == (L-1)/2 ? I1 : I1+1);
if(I1>=_O && dt[_I][I1] >= _K) {_C = I1; _E = (_S+_E)/2-1;}
else {_C = I2; _S = (_S+_E)/2+1; _K -= (I1>=_O ? dt[_I][I1] : 0);}
kth();
}
void calc (vector<ll> &D, vector<ll> &V, int O) {
for(int i=0;i<O;i++) D[i] = 0;
D[O] = 1;
for(int i=O+1;i<V.size();i++) {
int I1 = geti(V, i, (V[i]-1)/2), I2 = (V[i]/2 == (V[i]-1)/2 ? I1 : I1+1);
D[i] = (I1 != -1 ? D[I1] : 0) + (I2 != -1 ? D[I2] : 0);
}
}
int main() {
scanf("%lld%d%d",&l,&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
a[n+1] = l+1;
for(int 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(int i=1;i<=n+1;i++) {
cur[i] = v[i].size();
dt[i].resize(v[i].size());
if(--cur[i] >= 0) {
calc(dt[i], v[i], cur[i]);
pq.push({v[i][cur[i]], -i});
}
}
int cq = 1; ll dn = n;
for(int i=1;i<=m;i++) {
scanf("%lld",&qry[i]);
if(qry[i] <= n) {
printf("%lld\n",a[qry[i]]); cq++;
}
}
while(!pq.empty()) {
int C = -pq.top().second; ll V = dt[C][v[C].size()-1]; pq.pop();
for(;cq <= m && qry[cq] <= dn + V; cq++) {
_S = a[C-1]+1; _E = a[C]-1, _K = qry[cq] - dn;
_I = C; _C = v[C].size()-1, _O = cur[C];
kth();
}
if(cq > m) break; dn += V;
if(--cur[C] >= 0) {
calc(dt[C], v[C], cur[C]);
pq.push({v[C][cur[C]], -C});
}
}
}
Compilation message
ogledala.cpp: In function 'void calc(std::vector<long long int>&, std::vector<long long int>&, int)':
ogledala.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=O+1;i<V.size();i++) {
^
ogledala.cpp: In function 'int main()':
ogledala.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<v[i].size();j++) {
^
ogledala.cpp:42:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%d%d",&l,&n,&m);
^
ogledala.cpp:43:43: 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:63:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&qry[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
8664 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8664 KB |
Output is correct |
| 3 |
Correct |
36 ms |
9992 KB |
Output is correct |
| 4 |
Correct |
33 ms |
10036 KB |
Output is correct |
| 5 |
Correct |
99 ms |
16364 KB |
Output is correct |
| 6 |
Correct |
89 ms |
16784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
353 ms |
101608 KB |
Output is correct |
| 4 |
Correct |
309 ms |
102748 KB |
Output is correct |
| 5 |
Correct |
369 ms |
106820 KB |
Output is correct |
| 6 |
Correct |
403 ms |
107884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2025 ms |
65412 KB |
Output is correct |
| 2 |
Correct |
2139 ms |
65100 KB |
Output is correct |
| 3 |
Correct |
3016 ms |
95856 KB |
Output is correct |
| 4 |
Correct |
3593 ms |
97476 KB |
Output is correct |
| 5 |
Execution timed out |
4000 ms |
106816 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
