#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 1e5 + 5;
ll m; int n, q;
ll a[MX], b[MX];
vector<pair<ll, ll> > split(ll len){
vector<pair<ll, ll> > rs;
if(len == 0) return rs;
rs.push_back({len + 1, 0});
rs.push_back({len, 1}); // v[2i].first = v[2i+1].first + 1 to deal with parity
for(int i = 0; i < rs.size(); i += 2){
ll nlen1 = rs[i].first / 2, ncnt1 = rs[i].second;
ll nlen2 = (rs[i + 1].first - 1) / 2, ncnt2 = rs[i + 1].second;
if((rs[i].first - 1) / 2 == nlen1) ncnt1 += rs[i].second;
else ncnt2 += rs[i].second;
if(rs[i + 1].first / 2 == nlen1) ncnt1 += rs[i + 1].second;
else ncnt2 += rs[i + 1].second;
if(!nlen1 && !nlen2) break;
rs.push_back({nlen1, ncnt1}); rs.push_back({nlen2, ncnt2});
}
for(; rs.size() && rs.back().first == 0; rs.pop_back());
ll cnt1 = 0ll;
for(; rs.size() && rs.back().first == 1; rs.pop_back()) cnt1 += rs.back().second;
if(cnt1) rs.push_back({1, cnt1});
return rs;
}
ll find_pos(int i, ll find_len, ll find_id){
ll offset = a[i] + 1, len = a[i + 1] - a[i] - 1;
for(; len > find_len;){
vector<pair<ll, ll> > gt = split((len - 1) / 2);
ll cnt = 0ll;
for(auto i : gt) if(i.first == find_len) cnt += i.second;
if(cnt >= find_id){
len = (len - 1) / 2;
}else{
offset += 1 + (len - 1) / 2;
len = len - (1 + (len - 1) / 2);
find_id -= cnt;
}
}
return offset + (len - 1) / 2;
}
vector<pair<pair<ll, ll>, int> > seg;
int main(){
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 ++){
vector<pair<ll, ll> > gt = split(a[i + 1] - a[i] - 1);
for(auto j : gt) if(j.first > 0 && j.second > 0)
seg.push_back({j, i});
}
sort(seg.begin(), seg.end(), [&](pair<pair<ll, ll>, int> A, pair<pair<ll, ll>, int> B){
if(A.first.first == B.first.first) return A.second < B.second;
return A.first.first > B.first.first;
});
for(int i = 0; i < q; i ++)
scanf("%lld", &b[i]);
int idq = 0;
for(; idq < q && b[idq] <= n; idq ++) printf("%lld\n", a[b[idq]]);
ll offset = n + 1;
for(auto i : seg){
for(; idq < q && b[idq] < offset + i.first.second; idq ++)
printf("%lld\n", find_pos(i.second, i.first.first, b[idq] - offset + 1));
offset += i.first.second;
}
return 0;
}
Compilation message
ogledala.cpp: In function 'std::vector<std::pair<long long int, long long int> > split(long long int)':
ogledala.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i = 0; i < rs.size(); i += 2){
| ~~^~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%lld %d %d", &m, &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ogledala.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%lld", &a[i]);
| ~~~~~^~~~~~~~~~~~~~~
ogledala.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%lld", &b[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
50 ms |
2416 KB |
Output is correct |
| 4 |
Correct |
41 ms |
2584 KB |
Output is correct |
| 5 |
Correct |
72 ms |
7292 KB |
Output is correct |
| 6 |
Correct |
61 ms |
7364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
608 KB |
Output is correct |
| 2 |
Correct |
36 ms |
624 KB |
Output is correct |
| 3 |
Correct |
871 ms |
198088 KB |
Output is correct |
| 4 |
Correct |
851 ms |
198200 KB |
Output is correct |
| 5 |
Correct |
952 ms |
198208 KB |
Output is correct |
| 6 |
Correct |
976 ms |
198124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1016 ms |
99644 KB |
Output is correct |
| 2 |
Correct |
994 ms |
99708 KB |
Output is correct |
| 3 |
Correct |
1759 ms |
198188 KB |
Output is correct |
| 4 |
Correct |
1809 ms |
198116 KB |
Output is correct |
| 5 |
Correct |
2737 ms |
198256 KB |
Output is correct |
| 6 |
Correct |
2695 ms |
198140 KB |
Output is correct |
