# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1213764 | jerzyk | Bitaro's travel (JOI23_travel) | C++20 | 222 ms | 8312 KiB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<18;
ll tab[N];
int drzmi[2 * N], drzma[2 * N];
int GetL(int v, int x)
{
v += N;
while(v > 1)
{
if(v % 2 == 1 && drzma[v - 1] > x)
{--v; break;}
v /= 2;
}
//if(v == 1) return -1;
while(v < N)
{
v *= 2;
if(drzma[v + 1] >= x) ++v;
}
return v - N;
}
int GetR(int v, int x)
{
v += N;
while(v > 1)
{
if(v % 2 == 0 && drzmi[v + 1] <= x)
{++v; break;}
v /= 2;
}
//if(v == 1) return -1;
while(v < N)
{
v *= 2; ++v;
if(drzmi[v - 1] <= x) --v;
}
return v - N;
}
ll Query(int n, ll s)
{
ll ans = 0LL;
int cur = (lower_bound(tab + 1, tab + 1 + n, s) - tab);
if(tab[cur] - s >= s - tab[cur - 1])
--cur;
ans = tab[cur] - s;
if(ans < 0) ans *= -1LL;
int l = cur, r = cur, a;
while(l != 1 || r != n)
{
// cout << "Q: " << l << " " << r << " " << cur << "\n";
// cout << tab[l - 1] << " " << tab[r + 1] << "\n";
if(tab[cur] - tab[l - 1] <= tab[r + 1] - tab[cur])
{
// cout << "L:\n";
a = GetL(l, tab[r + 1]);
ans += tab[cur] - tab[a];
l = a; cur = a;
}else
{
// cout << "R:\n";
a = GetR(r, tab[l - 1]);
ans += tab[a] - tab[cur];
r = a; cur = a;
}
}
return ans;
}
void Solve()
{
int n, q, a;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> tab[i];
tab[n + 1] = II + 100;
tab[0] = -II;
drzmi[n + N] = -II - 300;
for(int i = 1; i < n; ++i)
drzmi[i + N] = tab[i] - (tab[i + 1] - tab[i]);
drzma[1 + N] = II + 300;
for(int i = 2; i <= n; ++i)
drzma[i + N] = tab[i] + (tab[i] - tab[i - 1]);
for(int v = N - 1; v >= 1; --v)
{
drzmi[v] = min(drzmi[v * 2], drzmi[v * 2 + 1]);
drzma[v] = max(drzma[v * 2], drzma[v * 2 + 1]);
}
cin >> q;
for(int i = 1; i <= q; ++i)
{
cin >> a;
ll ans = 0LL;
ans = Query(n, a);
cout << ans << "\n";
}
}
int main()
{
for(int i = 1; i < 2 * N; ++i) drzmi[i] = II;
for(int i = 1; i < 2 * N; ++i) drzma[i] = -II;
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |