| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 139306 |
2019-07-31T14:27:44 Z |
BThero |
Shortcut (IOI16_shortcut) |
C++17 |
|
248 ms |
313464 KB |
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "shortcut.h"
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN = (int)1e5 + 5;
const int MAXP = (int)1e7 + 5;
const ll INF = (ll)1e17;
struct Rect {
ll lx, rx, ly, ry;
Rect() {
lx = ly = -INF;
rx = ry = INF;
}
Rect(ll lx, ll rx, ll ly, ll ry)
: lx(lx), rx(rx), ly(ly), ry(ry) {}
void operator = (Rect b) {
lx = b.lx;
ly = b.ly;
rx = b.rx;
ry = b.ry;
}
};
Rect combine(Rect a, Rect b) {
return Rect(max(a.lx, b.lx), min(a.rx, b.rx), max(a.ly, b.ly), min(a.ry, b.ry));
}
ll w[MAXN], d[MAXN], p[MAXN];
int c1[MAXP], c2[MAXP];
Rect T[MAXP];
int root, sz;
int n;
ll k;
int newVer() {
T[sz] = Rect();
c1[sz] = c2[sz] = -1;
return sz++;
}
void update(int &v, ll tl, ll tr, ll p, Rect x) {
if (v == -1) {
v = newVer();
}
if (tl == tr) {
T[v] = combine(T[v], x);
return;
}
ll mid = (tl + tr) >> 1;
if (p <= mid) {
update(c1[v], tl, mid, p, x);
}
else {
update(c2[v], mid + 1, tr, p, x);
}
T[v] = Rect();
if (c1[v] != -1) {
T[v] = combine(T[v], T[c1[v]]);
}
if (c2[v] != -1) {
T[v] = combine(T[v], T[c2[v]]);
}
}
Rect query(int &v, ll tl, ll tr, ll l, ll r) {
if (l > r || tl > r || tr < l || v == -1) {
return Rect();
}
if (l <= tl && tr <= r) {
return T[v];
}
ll mid = (tl + tr) >> 1;
return combine(query(c1[v], tl, mid, l, r), query(c2[v], mid + 1, tr, l, r));
}
bool check(ll lim) {
ll tax = -INF, tbx = INF;
ll tay = -INF, tby = INF;
//for (int i = 1; i <= n; ++i) {
//Rect cur = query(root, -INF, INF, lim + p[i - 1] - d[i] + 1, INF);
//tax = max(tax, p[i - 1] + d[i] - lim + k + cur.lx);
//tbx = min(tbx, p[i - 1] - d[i] + lim - k + cur.rx);
//tay = max(tay, p[i - 1] + d[i] - lim + k + cur.ly);
//tby = min(tby, p[i - 1] - d[i] + lim - k + cur.ry);
//}
for (int a = 1; a <= n; ++a) {
for (int b = a + 1; b <= n; ++b) {
if (d[a] + d[b] + p[b - 1] - p[a - 1] <= lim) {
continue;
}
ll cx = p[a - 1] + p[b - 1];
ll cy = p[a - 1] - p[b - 1];
ll r = lim - k - d[a] - d[b];
if (r < 0) {
return 0;
}
ll ax = cx - r, bx = cx + r;
ll ay = cy - r, by = cy + r;
tax = max(tax, ax);
tbx = min(tbx, bx);
tay = max(tay, ay);
tby = min(tby, by);
}
}
//for (int a = 1; a < n; ++a) {
//for (int b = a + 1; b <= n; ++b) {
//ll cx = p[a - 1] + p[b - 1];
//ll cy = p[a - 1] - p[b - 1];
//if (tax <= cx && cx <= tbx) {
//if (tay <= cy && cy <= tby) {
//return 1;
//}
//}
//}
//}
for (int b = n; b > 1; --b) {
ll l = tax - p[b - 1];
ll r = tbx - p[b - 1];
l = max(l, tay + p[b - 1]);
r = min(r, tby + p[b - 1]);
int pos = lower_bound(p, p + n, l) - p + 1;
if (pos < b && p[pos] <= r) {
return 1;
}
}
return 0;
}
ll solve() {
for (int i = 1; i < n; ++i) {
p[i] = p[i - 1] + w[i];
}
root = -1;
for (int i = 1; i <= n; ++i) {
Rect cur;
cur.lx = p[i - 1] + d[i];
cur.rx = p[i - 1] - d[i];
cur.ly = -p[i - 1] + d[i];
cur.ry = -p[i - 1] - d[i];
update(root, -INF, INF, d[i] + p[i - 1], cur);
}
ll l = 0, r = INF, ans = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return ans;
}
ll find_shortcut(int _n, vector<int> l, vector<int> _d, int c) {
n = _n;
k = c;
for (int i = 1; i < n; ++i) {
w[i] = l[i - 1];
}
for (int i = 1; i <= n; ++i) {
d[i] = _d[i - 1];
}
return solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
313464 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
