#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
int m, n, q;
vector <int> points, interval;
set <int> found;
vector <int> numbers, all;
vector <vector<pair<int, int> > > dp, sayi; // [numberindex][nomeaning]
// {includesthisindex, with this freq}
void findnumbers(int x) {
if(x == 0) return;
found.insert(x);
int f = (x - 1) / 2, s = x / 2;
if(!found.count(f)) findnumbers(f);
if(x % 2 == 0 and !found.count(s)) findnumbers(s);
}
int find(int x) {
return (lower_bound(numbers.begin(), numbers.end(), x) - numbers.begin());
}
int finding(int dpindex, int search) {
int l = 0, r = dp[dpindex].size();
while(r - l > 1) {
int m = (r + l) / 2;
if(dp[dpindex][m].first > search) {
r = m;
}
else {
l = m;
}
}
return l;
}
void calc(int numindex) {
int x = numbers[numindex];
int f = (x - 1) / 2, s = x / 2;
if(x == 2) {
dp[numindex] = dp[find(f)];
}
if(x <= 2) {
dp[numindex].push_back({numindex, 1});
return;
}
if(x % 2) {
for(auto &[index, val]:dp[find(f)]) {
dp[numindex].push_back({index, val * 2});
}
}
else {
vector <pair<int, int> > tempv = dp[find(f)];
for(auto &[index, val]:dp[find(s)]) {
tempv.push_back({index, val});
}
sort(tempv.begin(), tempv.end());
for(int i = 0; i < tempv.size(); i++){
int val = tempv[i].second;
if(i < tempv.size() - 1 and tempv[i].first == tempv[i + 1].first) {
val += tempv[i + 1].second;
i++;
}
dp[numindex].push_back({tempv[i].first, val});
}
}
dp[numindex].push_back({numindex, 1});
}
int32_t main(){
fast
cin>>m>>n>>q;
points.push_back(0);
for(int i = 1; i <= n; i++) {
int in;
cin>>in;
points.push_back(in);
}
points.push_back(m + 1);
for(int i = 0; i <= n; i++) {
interval.push_back(points[i + 1] - points[i] - 1);
findnumbers(interval[i]);
}
dp.resize(found.size());
all.resize(found.size());
sayi.resize(found.size());
for(auto it:found) {
numbers.push_back(it);
calc(numbers.size() - 1);
}
for(int i = 0; i <= n; i++) {
int st = points[i], length = interval[i];
if(length == 0) continue;
for(auto &[index, freq]:dp[find(length)]) {
all[index] += freq;
sayi[index].push_back({i, freq});
}
}
// int time = 0;
// for(auto it:sayi) {
// cout<<numbers[time]<<":\n";
// for(auto itt:it) {
// cout<<itt.first<<" "<<itt.second<<"\n";
// }
// time++;
// }
int allindex = numbers.size() - 1, sayindex = 0, gone = 0;
for(int i = 0; i < q; i++) {
int query;
cin>>query;
if(query <= n) {
cout<<points[query]<<"\n";
continue;
}
query -= n;
int rem = query - gone, val;
while(true) {
val = sayi[allindex][sayindex].second;
if(val >= rem) break;
gone += val;
rem -= val;
sayindex++;
if(sayindex == sayi[allindex].size()) allindex--, sayindex = 0;
}
int intervalIndex = sayi[allindex][sayindex].first;
// use rem to navigate inside the interval
val = interval[intervalIndex];
int stpoint = points[intervalIndex];
int add = 0;
// allindexe göre searchla
// cout<<numbers[allindex]<<":\n";
while(val > numbers[allindex]) {
// cout<<val<<" "<<add<<" "<<rem<<"\n";
int f = (val - 1) / 2, s = val / 2;
int findex = find(f);
int underindex = finding(findex, allindex);
if(!f or dp[findex][underindex].first != allindex) {
// cout<<"right1\n";
add += f + 1;
val = s;
continue;
}
int leftfreq = dp[findex][underindex].second;
if(leftfreq >= rem) {
// cout<<"left\n";
val = f;
}
else {
// cout<<"right\n";
add += f + 1;
rem -= leftfreq;
val = s;
}
}
// cout<<val<<"\n";
add += (val - 1) / 2;
cout<<add + stpoint + 1<<"\n";
}
}
Compilation message
ogledala.cpp: In function 'void calc(long long int)':
ogledala.cpp:61:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < tempv.size(); i++){
| ~~^~~~~~~~~~~~~~
ogledala.cpp:63:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(i < tempv.size() - 1 and tempv[i].first == tempv[i + 1].first) {
| ~~^~~~~~~~~~~~~~~~~~
ogledala.cpp: In function 'int32_t main()':
ogledala.cpp:95:7: warning: unused variable 'st' [-Wunused-variable]
95 | int st = points[i], length = interval[i];
| ^~
ogledala.cpp:126:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | if(sayindex == sayi[allindex].size()) allindex--, sayindex = 0;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
15 ms |
2252 KB |
Output is correct |
| 4 |
Correct |
14 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
30 ms |
6776 KB |
Output is correct |
| 6 |
Correct |
31 ms |
7180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2908 KB |
Output is correct |
| 3 |
Runtime error |
1290 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
649 ms |
159304 KB |
Output is correct |
| 2 |
Correct |
649 ms |
152864 KB |
Output is correct |
| 3 |
Runtime error |
1144 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
