| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 642160 | messiuuuuu | OGLEDALA (COI15_ogledala) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///
#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5 + 5;
const ll INF = 1e18 + 5;
struct TLine
{
ll le, sl;
int id;
};
vector<TLine> all;
map<ll, ll> mp;
void Proc(ll l, ll r, ll le)
{
mp.clear();
if (l > r)
return;
deque<ll> Q;
mp[r - l + 1] = 1;
Q.pb(r - l + 1);
while (!Q.empty())
{
ll u = Q.front();
ll d = mp[u];
Q.pop_front();
ll t = u >> 1;
if (t >= le && !mp.count(t))
Q.pb(t);
mp[t] += d;
u--;
t = u >> 1;
if (t >= le && !mp.count(t))
Q.pb(t);
mp[t] += d;
}
}
int n, q;
ll m;
pair<ll, ll> b[MAXN];
ll a[MAXN];
pair<int, int> con[MAXN][100];
map<ll, int> mp1[MAXN];
void Input()
{
cin >> m >> n >> q;
ll last = 0;
for (int i = 1; i <= n + 1; i++)
{
if (i <= n)
cin >> a[i];
else
a[i] = m + 1;
b[i] = {last + 1, a[i] - 1};
Proc(last + 1, a[i] - 1, 2);
int cnt = 0;
for (const auto& p : mp)
{
all.pb({p.fi, p.se, i});
ll num = p.fi;
mp1[i][num] = ++cnt;
//if (m <= 3e5 || n <= 1e3)
con[i][mp1[i][num]] = make_pair(mp1[i][num / 2], mp1[i][(num - 1) / 2]);
}
last = a[i];
}
}
ll res;
int ID;
ll cal[100];
void Cal(ll l, ll r, int le)
{
memset(cal, 0, sizeof(cal));
if (l > r)
return;
deque<int> Q;
cal[mp1[ID][r - l + 1]] = 1;
Q.pb(mp1[ID][r - l + 1]);
int cnt = 0;
while (!Q.empty())
{
int u = Q.front();
Q.pop_front();
int t = con[ID][u].fi;
if (t >= le && !cal[t])
Q.pb(t);
cal[t] += cal[u];
t = con[ID][u].se;
if (t >= le && !cal[t])
Q.pb(t);
cal[t] += cal[u];
}
}
void Dnc(ll l, ll r, ll le, ll sl)
{
if (r - l + 1 == le)
{
res = (l + r) >> 1;
return;
}
ll mid = (l + r) >> 1;
Cal(l, mid - 1, mp1[ID][le]);
if (sl <= cal[mp1[ID][le]])
{
Dnc(l, mid - 1, le, sl);
} else
{
sl -= cal[mp1[ID][le]];
Dnc(mid + 1, r, le, sl);
}
}
void Solve()
{
sort(all.begin(), all.end(), [](const auto& i, const auto& j)
{
return i.le > j.le || i.le == j.le && i.id < j.id;
});
//cerr << all[0].sl << '\n';
sum[0] = all[0].sl;
for (int i = 1; i < all.size(); i++)
sum[i] = sum[i - 1] + all[i].sl;
ll sum = 0;
int p = 0;
while (q-- > 0)
{
ll c;
cin >> c;
if (c <= n)
{
cout << a[c] << '\n';
continue;
}
c -= n;
while (p < all.size() && sum + all[p].sl < c)
{
sum += all[p].sl;
p++;
}
//cerr << p << '\n';
c -= sum;
//cerr << c << '\n';
res = -1;
ID = all[p].id;
Dnc(b[ID].fi, b[ID].se, all[p].le, c);
cout << res << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(task".INP","r"))
{
freopen(task".INP","r",stdin);
freopen(task".OUT","w",stdout);
}
Input();
//if (m <= 3e5 || n <= 1e3)
Solve();
//else
return 0;
{
while (q-- > 0)
{
ll x;
cin >> x;
cout << 0 << '\n';
}
}
}