#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <bitset>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7, INF = 1e18 + 1;
using namespace std;
unordered_map <ll, vector < pair <ll, ll> > > d;
ll a[100000], n, m, q;
void calc (ll x)
{
if (d.find (x) != d.end ()) return;
if (!x) return;
ll l = (x - 1) / 2, r = x - 1 - l;
calc (l);
calc (r);
ll ptr1 = 0, ptr2 = 0;
auto &v = d[x], &v_l = d[l], &v_r = d[r];
while (ptr1 != v_l.size () || ptr2 != v_r.size ())
{
if (ptr1 != v_l.size () && ptr2 != v_r.size () && v_l[ptr1].first == v_r[ptr2].first)
{
v.emplace_back (v_l[ptr1].first, v_l[ptr1].second + v_r[ptr2].second);
ptr1++;
ptr2++;
continue;
}
if (ptr1 < v_l.size () && (ptr2 == v_r.size () || v_l[ptr1] < v_r[ptr2]))
{
v.push_back (v_l[ptr1]);
ptr1++;
}
else
{
v.push_back (v_r[ptr2]);
ptr2++;
}
}
v.emplace_back (x, 1);
}
ll ord_stat (ll x, ll c, ll len, ll l, ll r)
{
if (len == x) return (l + r) / 2;
ll m = (l + r) / 2;
ll len_l = (len - 1) / 2, len_r = len - 1 - len_l;
auto& v_l = d[len_l], v_r = d[len_r];
ll k = lower_bound (v_l.begin (), v_l.end (), make_pair (x, 0LL)) - v_l.begin ();
if (k != v_l.size () && v_l[k].first == x)
{
if (v_l[k].second >= c) return ord_stat (x, c, len_l, l, m - 1);
else return ord_stat (x, c - v_l[k].second, len_r, m + 1, r);
}
else return ord_stat (x, c, len_r, m + 1, r);
}
struct seg
{
ll x, c, i;
bool operator < (const seg& b) const
{
return (x == b.x ? i < b.i : x > b.x);
}
};
vector <seg> v;
int main ()
{
cin >> m >> n >> q;
for (ll i = 0; i < n; i++)
{
scanf ("%lld", &a[i]);
if (i) calc (a[i] - a[i-1] - 1);
else calc (a[i] - 1);
}
calc (m - (n ? a[n-1] : 0));
for (ll i = 0; i < n; i++)
for (auto x : d[a[i] - (i ? a[i-1] : 0) - 1])
v.push_back ({x.first, x.second, i});
for (auto x : d[m - (n ? a[n-1] : 0)])
v.push_back ({x.first, x.second, n});
sort (v.begin(), v.end());
ll sum = 0, ptr = 0;
for (ll i = 0; i < q; i++)
{
ll b;
scanf ("%lld", &b);
if (b <= n)
{
printf ("%lld\n", a[b-1]);
continue;
}
b -= n;
if (sum + v[ptr].c < b)
{
do
{
sum += v[ptr].c;
ptr++;
}
while (ptr != v.size () && sum + v[ptr].c < b);
}
ll l = (v[ptr].i ? a[v[ptr].i - 1] + 1 : 1), r = (v[ptr].i != n ? a[v[ptr].i] - 1 : m);
printf ("%lld\n", ord_stat (v[ptr].x, b - sum, r - l + 1, l, r));
}
}
Compilation message
ogledala.cpp: In function 'void calc(ll)':
ogledala.cpp:40:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 != v_l.size () || ptr2 != v_r.size ())
~~~~~^~~~~~~~~~~~~~
ogledala.cpp:40:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 != v_l.size () || ptr2 != v_r.size ())
~~~~~^~~~~~~~~~~~~~
ogledala.cpp:42:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ptr1 != v_l.size () && ptr2 != v_r.size () && v_l[ptr1].first == v_r[ptr2].first)
~~~~~^~~~~~~~~~~~~~
ogledala.cpp:42:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ptr1 != v_l.size () && ptr2 != v_r.size () && v_l[ptr1].first == v_r[ptr2].first)
~~~~~^~~~~~~~~~~~~~
ogledala.cpp:52:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ptr1 < v_l.size () && (ptr2 == v_r.size () || v_l[ptr1] < v_r[ptr2]))
~~~~~^~~~~~~~~~~~~
ogledala.cpp:52:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ptr1 < v_l.size () && (ptr2 == v_r.size () || v_l[ptr1] < v_r[ptr2]))
~~~~~^~~~~~~~~~~~~~
ogledala.cpp: In function 'll ord_stat(ll, ll, ll, ll, ll)':
ogledala.cpp:78:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k != v_l.size () && v_l[k].first == x)
~~^~~~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:140:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr != v.size () && sum + v[ptr].c < b);
~~~~^~~~~~~~~~~~
ogledala.cpp:104:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%lld", &a[i]);
~~~~~~^~~~~~~~~~~~~~~
ogledala.cpp:126:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%lld", &b);
~~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
49 ms |
2412 KB |
Output is correct |
| 4 |
Correct |
43 ms |
2536 KB |
Output is correct |
| 5 |
Correct |
78 ms |
8292 KB |
Output is correct |
| 6 |
Correct |
73 ms |
8288 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
17 ms |
2808 KB |
Output is correct |
| 3 |
Runtime error |
1307 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1456 ms |
192956 KB |
Output is correct |
| 2 |
Correct |
1375 ms |
181580 KB |
Output is correct |
| 3 |
Runtime error |
1353 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
