Submission #60390

#TimeUsernameProblemLanguageResultExecution timeMemory
60390kingpig9Shortcut (IOI16_shortcut)C++11
0 / 100
4 ms760 KiB
#include <bits/stdc++.h> #include "shortcut.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ll, int> edge; const int MAXN = 1 << 20; #define debug(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) template<class T> void setmin (T &a, T b) { if (b < a) { a = b; } } template<class T> void setmax (T &a, T b) { if (a < b) { a = b; } } int N; ll C; ll L[MAXN]; //length from (i-1) to i ll PL[MAXN]; ll D[MAXN]; //distance to secondary station (i + N) bool moo_slow (ll dia) { //is diameter <= dia? ll xmymn = LLONG_MIN, xmymx = LLONG_MAX; ll xpymn = LLONG_MIN, xpymx = LLONG_MAX; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if ((D[i] - L[i]) + (D[j] + L[j]) > dia) { //ll lim = dia - D[i] - D[j] - C; //L[i] - L[j] - lim <= x - y <= L[i] - L[j] + lim //L[i] + L[j] - lim <= x + y <= L[i] + L[j] + lim setmax(xmymn, (L[i] + D[i]) + (-L[j] + D[j]) - dia + C); setmin(xmymx, (L[i] - D[i]) + (-L[j] - D[j]) + dia - C); setmax(xpymn, (L[i] + D[i]) + (L[j] + D[j]) - dia + C); setmin(xpymx, (L[i] - D[i]) + (L[j] - D[j]) + dia - C); } //otherwise everything works } } //debug("x - y: min = %lld, max = %lld.\nx + y: min = %lld, max = %lld.\n", xmymn, xmymx, xpymn, xpymx); if (xmymn > xmymx || xpymn > xpymx) { return false; } debug("xmymn = %lld, xmymx = %lld. xpymn = %lld, xpymx = %lld.\n", xmymn, xmymx, xpymn, xpymx); if (xmymn == LLONG_MIN) { return true; } //ok now check if anything is in there for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if (xmymn <= L[i] - L[j] && L[i] - L[j] <= xmymx) { if (xpymn <= L[i] + L[j] && L[i] + L[j] <= xpymx) { return true; } } } } return false; } //max segtree struct segtree { ll tree[2 * MAXN]; void update (int x, ll v) { for (tree[x += MAXN] = v; x >>= 1; ) { tree[x] = max(tree[2 * x], tree[2 * x + 1]); } } ll query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) { if (rt <= a || b <= lt) { return LLONG_MIN; } if (a <= lt && rt <= b) { return tree[cur]; } int mid = (lt + rt) / 2; return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt)); } }; segtree seglpd, segdml; bool moo (ll dia) { //debug("DIA = %lld\n", dia); //return moo_slow(dia); ll xmymn = LLONG_MIN, xmymx = LLONG_MAX; ll xpymn = LLONG_MIN, xpymx = LLONG_MAX; vector<pii> vdml, vdpl; for (int i = 0; i < N; i++) { vdml.push_back({D[i] - L[i], i}); vdpl.push_back({D[i] + L[i], i}); } sort(all(vdml)); sort(all(vdpl)); //reset entire segtree for (int i = 0; i < N; i++) { seglpd.update(i, LLONG_MIN); segdml.update(i, LLONG_MIN); } //vdml[vi].fi + vdpl[vj].fi > dia for (int vj = 0, vi = N; vj < N; vj++) { while (vi > 0 && vdml[vi - 1].fi + vdpl[vj].fi > dia) { //add it in vi--; //add vi int i = vdml[vi].se; seglpd.update(i, L[i] + D[i]); segdml.update(i, D[i] - L[i]); } //swatted by people int j = vdpl[vj].se; //setmax(xmymn, (L[i] + D[i]) + (-L[j] + D[j]) - dia + C); //setmin(xmymx, (L[i] - D[i]) + (-L[j] - D[j]) + dia - C); //setmax(xpymn, (L[i] + D[i]) + (L[j] + D[j]) - dia + C); //setmin(xpymx, (L[i] - D[i]) + (L[j] - D[j]) + dia - C); ll qulpd = seglpd.query(0, j), qudml = segdml.query(0, j); if (qulpd != LLONG_MIN) { setmax(xmymn, qulpd + (-L[j] + D[j]) - dia + C); setmax(xpymn, qulpd + (L[j] + D[j]) - dia + C); } if (qudml != LLONG_MIN) { setmin(xmymx, -qudml + (-L[j] - D[j]) + dia - C); setmin(xpymx, -qudml + (L[j] - D[j]) + dia - C); } } //debug("xmymn = %lld, xmymx = %lld. xpymn = %lld, xpymx = %lld.\n", xmymn, xmymx, xpymn, xpymx); //basic checks if (xmymn > xmymx || xpymn > xpymx) { return false; } if (xmymn == LLONG_MIN) { return true; } for (int j = 1; j < N; j++) { ll xmn = max(xpymn - L[j], xmymn + L[j]); ll xmx = min(xpymx - L[j], xmymx + L[j]); if (xmn > xmx) { continue; } if (upper_bound(L, L + j, xmx) != lower_bound(L, L + j, xmn)) { return true; } } return false; } ll find_shortcut (int nnn, vector<int> lll, vector<int> ddd, int ccc) { //very very preliminary stuff - should also init other stuff N = nnn; C = ccc; for (int i = 1; i < N; i++) { L[i] = L[i - 1] + lll[i - 1]; } for (int i = 0; i < N; i++) { D[i] = ddd[i]; } ll lo = 0, hi = (N + 1) * 1000000000ll; while (hi - lo > 1) { ll mid = (lo + hi) >> 1; if (moo(mid)) { hi = mid; } else { lo = mid; } } return hi; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...