# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
619165 |
2022-08-02T10:20:41 Z |
Drew_ |
OGLEDALA (COI15_ogledala) |
C++17 |
|
778 ms |
317284 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define size(x) (int)x.size()
using ii = pair<int, int>;
using ll = long long;
using pl = pair<ll, ll>;
const int MAX = 1e5 + 69;
const ll inf = 1e18 + 69;
ll M, N, Q;
ll A[MAX], B[MAX], Blen[MAX], Bpos[MAX], Bblank[MAX];
ll ans[MAX];
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> M >> N >> Q;
for (int i = 1; i <= N; ++i)
cin >> A[i];
int si = 1;
for (int i = 1; i <= Q; ++i)
{
cin >> B[i];
if (B[i] <= N)
ans[i] = A[B[i]], si++;
B[i] -= N;
}
A[0] = 0; A[N+1] = M+1;
vector<pl> len;
for (int i = 0; i <= N; ++i) if (A[i+1] - A[i] - 1)
len.pb({A[i+1] - A[i] - 1, A[i] + 1});
map<ll, ll> fq;
priority_queue<ll> pq;
for (auto [l, x] : len)
{
if (!fq.count(l))
pq.push(l);
fq[l]++;
}
const auto genfq = [&]()
{
while (!pq.empty())
{
ll val = pq.top(); pq.pop();
if ((val-1) >> 1)
{
if (!fq.count((val-1) >> 1))
pq.push((val-1) >> 1);
fq[(val-1) >> 1] += fq[val];
}
if (val >> 1)
{
if (!fq.count(val >> 1))
pq.push(val >> 1);
fq[val >> 1] += fq[val];
}
}
};
genfq();
vector<ll> zip;
for (const auto &[x, y] : fq)
zip.pb(x);
// cerr << "zip: ";
// for (int x : zip)
// cerr << x << ", ";
// cerr << '\n';
vector<ii> nxt(size(fq)); // division by 2
for (int a = 0; a < size(zip); ++a)
{
ll L = (zip[a]-1) >> 1, R = (zip[a]) >> 1;
int i = -1, j = -1;
if (L > 0) i = (int)(lower_bound(zip.begin(), zip.end(), L) - zip.begin());
if (R > 0) j = (int)(lower_bound(zip.begin(), zip.end(), R) - zip.begin());
nxt[a] = { i, j };
}
vector<vector<int>> impt(size(zip));
for (int i = 0; i < size(zip); ++i)
{
impt[i].pb(i);
if (nxt[i].f1 != -1) for (int x : impt[nxt[i].f1])
impt[i].pb(x);
if (nxt[i].s2 != -1) for (int x : impt[nxt[i].s2])
impt[i].pb(x);
sort(impt[i].begin(), impt[i].end());
impt[i].resize(unique(impt[i].begin(), impt[i].end()) - impt[i].begin());
}
vector<ll> ctr(size(zip));
vector<queue<pl>> memo(size(zip));
{
vector<pl> vec(fq.rbegin(), fq.rend());
for (int i = 0; i < size(vec); ++i)
vec[i].f1 = (int)(lower_bound(zip.begin(), zip.end(), vec[i].f1) - zip.begin());
for (int i = 1; i < size(vec); ++i)
vec[i].s2 += vec[i-1].s2;
for (int i = si, j = 0; i <= Q; ++i)
{
while (vec[j].s2 < B[i])
++j;
Blen[i] = vec[j].f1;
Bpos[i] = B[i] - (j ? vec[j-1].s2 : 0);
memo[Blen[i]].push({Bpos[i], i});
}
}
vector<ll> freq(size(zip));
for (int i = 0; i < size(len); ++i)
{
auto [l, x] = len[i];
int id = (int)(lower_bound(zip.begin(), zip.end(), l) - zip.begin());
for (int j : impt[id])
freq[j] = 0;
freq[id] = 1;
for (int j = size(impt[id]) - 1; j >= 0; --j)
{
auto [a, b] = nxt[impt[id][j]];
if (a != -1)
freq[a] += freq[impt[id][j]];
if (b != -1)
freq[b] += freq[impt[id][j]];
}
vector<pl> vec;
for (int j = size(impt[id]) - 1; j >= 0; --j)
vec.pb({impt[id][j], freq[impt[id][j]]});
// there are ~(log MAX) values
for (auto [x, y] : vec)
{
ctr[x] += y;
while (!memo[x].empty() && memo[x].front().f1 <= ctr[x])
{
Bpos[memo[x].front().s2] -= ctr[x] - y;
Bblank[memo[x].front().s2] = i;
memo[x].pop();
}
}
}
for (auto &i : freq)
i = 0;
for (int i = si; i <= Q; ++i)
{
auto [val, pos] = len[Bblank[i]];
int id = (lower_bound(zip.begin(), zip.end(), val) - zip.begin());
for (;;)
{
if (id == Blen[i])
{
ans[i] = pos + (zip[id]-1) / 2;
break;
}
// check to go to left or right
ll L = nxt[id].f1, R = nxt[id].s2;
if (L == -1)
{
id = R, pos++;
continue;
}
for (int j : impt[L])
freq[j] = 0;
freq[L] = 1;
for (int j = size(impt[L]) - 1; j >= 0; --j)
{
if (impt[L][j] < Blen[i])
break;
auto [a, b] = nxt[impt[L][j]];
if (a >= Blen[i])
freq[a] += freq[impt[L][j]];
if (b >= Blen[i])
freq[b] += freq[impt[L][j]];
}
for (int j : impt[L])
freq[j] = 0;
// cerr << "freq: ";
// for (int i = 0; i < size(zip); ++i)
// cerr << freq[i] << ", ";
// cerr << '\n';
if (Bpos[i] <= freq[Blen[i]]) id = L;
else id = R, pos += zip[L] + 1, Bpos[i] -= freq[Blen[i]];
}
}
for (int i = 1; i <= Q; ++i)
cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
11 ms |
7308 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
778 ms |
317284 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |