#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;
vector <int> ufound, found;
vector <int> numbers;
vector <vector<pair<int, int> > > dp, sayi; // [numberindex][nomeaning]
// {includesthisindex, with this freq}
void findnumbers(int x) {
if(x == 0) return;
int x1 = x, x2 = x;
while(x1 or x2) {
if(x1) found.push_back(x1);
if(x2) found.push_back(x2);
int f = (x1 - 1) / 2, s = x1 / 2, ff = (x2 - 1) / 2, ss = x2 / 2;
set <int> st;
st.insert(f);
st.insert(s);
st.insert(ff);
st.insert(ss);
vector <int> bro;
for(auto it:st) {
bro.push_back(it);
}
bro.push_back(bro[0]);
x1 = bro[0], x2 = bro[1];
}
}
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]);
}
sort(found.begin(), found.end());
found.push_back(inf);
for(int i = 0; i < found.size() - 1; i++) {
if(found[i] != found[i+1]) {
ufound.push_back(found[i]);
}
}
dp.resize(ufound.size());
sayi.resize(ufound.size());
for(auto it:ufound) {
// cout<<it<<" ";
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)]) {
sayi[index].push_back({i, freq});
}
}
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";
}
cerr<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds\n";
}
Compilation message
ogledala.cpp: In function 'void calc(long long int)':
ogledala.cpp:74: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]
74 | for(int i = 0; i < tempv.size(); i++){
| ~~^~~~~~~~~~~~~~
ogledala.cpp:76: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]
76 | if(i < tempv.size() - 1 and tempv[i].first == tempv[i + 1].first) {
| ~~^~~~~~~~~~~~~~~~~~
ogledala.cpp: In function 'int32_t main()':
ogledala.cpp:102:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i = 0; i < found.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~~
ogledala.cpp:115:7: warning: unused variable 'st' [-Wunused-variable]
115 | int st = points[i], length = interval[i];
| ^~
ogledala.cpp:137: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]
137 | if(sayindex == sayi[allindex].size()) allindex--, sayindex = 0;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
20 ms |
2328 KB |
Output is correct |
| 4 |
Correct |
19 ms |
2576 KB |
Output is correct |
| 5 |
Correct |
44 ms |
8552 KB |
Output is correct |
| 6 |
Correct |
47 ms |
10864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2692 KB |
Output is correct |
| 3 |
Runtime error |
1270 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
910 ms |
178476 KB |
Output is correct |
| 2 |
Correct |
891 ms |
173572 KB |
Output is correct |
| 3 |
Runtime error |
1197 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
