| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 620212 |
2022-08-03T03:48:24 Z |
Drew_ |
OGLEDALA (COI15_ogledala) |
C++17 |
|
3448 ms |
204916 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];
ll ans[MAX];
int32_t 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});
const auto gen = [&](ll val, ll bound = 1) -> vector<pl>
{
vector<pl> res;
queue<pl> q;
q.push({val, 1});
while (!q.empty())
{
auto [x, fq] = q.front(); q.pop();
while (!q.empty() && q.front().f1 == x)
fq += q.front().s2, q.pop();
res.pb({x, fq});
if ((x >> 1) >= bound) q.push({x >> 1, fq});
if (((x-1) >> 1) >= bound) q.push({(x-1) >> 1, fq});
}
return res;
};
vector<array<ll, 3>> all;
for (int i = 0; i < size(len); ++i)
{
vector<pl> v = gen(len[i].f1);
for (auto [x, fq] : v)
all.pb({x, fq, i});
}
sort(all.begin(), all.end(), [](array<ll, 3> &x, array<ll, 3> &y){
return x[0] > y[0] || (x[0] == y[0] && x[2] < y[2]);
});
ll sum = 0;
for (int i = si, j = 0; i <= Q; ++i)
{
while (sum < B[i])
sum += all[j++][1];
auto [val, fq, src] = all[j-1];
B[i] -= sum - fq;
for (auto [cur, pos] = len[src];;)
{
if (val == cur)
{
ans[i] = pos + ((val - 1) >> 1);
break;
}
// check to go to left or right
ll L = (cur-1) >> 1, R = (cur) >> 1;
if (L < val)
{
cur = R, pos += L+1;
continue;
}
vector<pl> v = gen(L, val);
if (v.back().f1 != val) cur = R, pos += L+1;
else if (B[i] <= v.back().s2) cur = L;
else cur = R, pos += L+1, B[i] -= v.back().s2;
}
}
for (int i = 1; i <= Q; ++i)
cout << ans[i] << "\n";
// vector<ii> nxt(size(zip), mp(-1, -1));
// for (int x = 0; x < size(zip); ++x)
// {
// if (((zip[x] - 1) >> 1) > 0)
// nxt[x].f1 = (int)(lower_bound(zip.begin(), zip.end(), (zip[x] - 1) >> 1) - zip.begin());
// if ((zip[x] >> 1) > 0)
// nxt[x].s2 = (int)(lower_bound(zip.begin(), zip.end(), zip[x] >> 1) - zip.begin());
// }
// vector<ll> freq(size(zip), 0);
// vector<ll> ctr(size(zip));
// vector<queue<pl>> memo(size(zip));
// {
// set<int, greater<int>> st;
// for (auto &[l, p] : len)
// {
// int id = (int)(lower_bound(zip.begin(), zip.end(), l) - zip.begin());
// freq[id]++;
// st.insert(id);
// }
// while (!st.empty())
// {
// int x = *st.begin(); st.erase(st.begin());
// if (nxt[x].f1 != -1) freq[nxt[x].f1] += freq[x], st.insert(nxt[x].f1);
// if (nxt[x].s2 != -1) freq[nxt[x].s2] += freq[x], st.insert(nxt[x].s2);
// }
// }
// {
// vector<pair<int, ll>> vec;
// for (int i = 0; i < size(zip); ++i)
// vec.pb({i, freq[i]});
// reverse(vec.begin(), vec.end());
// 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});
// }
// }
// for (int i = 0; i < size(len); ++i)
// {
// auto [l, p] = len[i];
// int id = (int)(lower_bound(zip.begin(), zip.end(), l) - zip.begin());
// set<int, greater<int>> st; st.insert(id);
// while (!st.empty())
// {
// int x = *st.begin(); st.erase(st.begin());
// freq[x] = 0;
// if (nxt[x].f1 != -1) st.insert(nxt[x].f1);
// if (nxt[x].s2 != -1) st.insert(nxt[x].s2);
// }
// st.insert(id); freq[id] = 1;
// vector<pl> vec;
// while (!st.empty())
// {
// int x = *st.begin(); st.erase(st.begin());
// vec.pb({x, freq[x]});
// if (nxt[x].f1 != -1) freq[nxt[x].f1] += freq[x], st.insert(nxt[x].f1);
// if (nxt[x].s2 != -1) freq[nxt[x].s2] += freq[x], st.insert(nxt[x].s2);
// }
// // 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();
// }
// }
// }
// fill(freq.begin(), freq.end(), 0);
// for (int i = si; i <= Q; ++i)
// {
// auto [val, pos] = len[Bblank[i]];
// int id = (int)(lower_bound(zip.begin(), zip.end(), val) - zip.begin());
// // cerr << "\n\n solving: " << i << " " << Blen[i] << " " << Bpos[i] << '\n';
// for (;;)
// {
// // cerr << "id: " << id << " " << pos << '\n';
// if (id == Blen[i])
// {
// ans[i] = pos + (zip[id]-1) / 2;
// break;
// }
// // check to go to left or right
// int L = nxt[id].f1, R = nxt[id].s2;
// if (L == -1)
// {
// id = R, pos++;
// continue;
// }
// set<int, greater<int>> st; st.insert(L);
// while (!st.empty())
// {
// int x = *st.begin(); st.erase(st.begin());
// freq[x] = 0;
// if (nxt[x].f1 != -1) st.insert(nxt[x].f1);
// if (nxt[x].s2 != -1) st.insert(nxt[x].s2);
// }
// st.insert(L); freq[L] = 1;
// vector<pl> vec;
// while (!st.empty())
// {
// int x = *st.begin(); st.erase(st.begin());
// vec.pb({x, freq[x]});
// if (nxt[x].f1 != -1) freq[nxt[x].f1] += freq[x], st.insert(nxt[x].f1);
// if (nxt[x].s2 != -1) freq[nxt[x].s2] += freq[x], st.insert(nxt[x].s2);
// }
// // cerr << "freq: ";
// // for (int zz = 0; zz < size(zip); ++zz)
// // cerr << freq[zz] << ", ";
// // cerr << '\n';
// // cerr << Bpos[i] << " and " << freq[Blen[i]] << '\n';
// // cerr << i << " -> " << Bpos[i] << " " << freq[Blen[i]] << " AKWOAK\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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
38 ms |
3784 KB |
Output is correct |
| 4 |
Correct |
31 ms |
3908 KB |
Output is correct |
| 5 |
Correct |
55 ms |
12228 KB |
Output is correct |
| 6 |
Correct |
55 ms |
12480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
664 KB |
Output is correct |
| 2 |
Correct |
18 ms |
724 KB |
Output is correct |
| 3 |
Correct |
926 ms |
204156 KB |
Output is correct |
| 4 |
Correct |
919 ms |
204160 KB |
Output is correct |
| 5 |
Correct |
1008 ms |
204304 KB |
Output is correct |
| 6 |
Correct |
1072 ms |
204360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1345 ms |
103472 KB |
Output is correct |
| 2 |
Correct |
1244 ms |
105640 KB |
Output is correct |
| 3 |
Correct |
2269 ms |
204484 KB |
Output is correct |
| 4 |
Correct |
2203 ms |
204484 KB |
Output is correct |
| 5 |
Correct |
3448 ms |
204808 KB |
Output is correct |
| 6 |
Correct |
3385 ms |
204916 KB |
Output is correct |
