Submission #423775

#TimeUsernameProblemLanguageResultExecution timeMemory
423775jtnydv25Shortcut (IOI16_shortcut)C++17
97 / 100
2077 ms93824 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define all(c) ((c).begin()), ((c).end()) #define sz(x) ((int)(x).size()) #ifdef LOCAL #include <print.h> #else #define trace(...) #define endl '\n' #endif const int N = 1 << 20; const ll INF = 1e18; struct Data{ ll a, b; Data() : a(-INF), b(INF){} Data(ll a, ll b) : a(a), b(b){} }; inline void merge(Data & X, const Data & Y){ X.a = max(X.a, Y.a); X.b = min(X.b,Y.b); } Data _data[N]; void init(){ for(int i = 0; i < N; i++) _data[i] = Data(); } inline void add(int i, Data d){ i++; for(; i < N; i += (i & (-i))){ merge(_data[i], d); } } Data get(int i){ i++; Data ret; for(; i; i -=(i & (-i))) merge(ret, _data[i]); return ret; } long long find_shortcut_old(int n, std::vector<int> l, std::vector<int> d, int c){ vector<ll> p(n); for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1]; vector<int> perm1(n), perm2(n); vector<int> where(n); iota(all(perm1), 0); iota(all(perm2), 0); sort(all(perm1), [&](int i, int j){return d[i] - p[i] > d[j] - p[j];}); sort(all(perm2), [&](int i, int j){return d[i] + p[i] < d[j] + p[j];}); for(int i = 0; i < n; i++) where[perm1[i]] = i; int mx = 0, mx2 = 0; for(int ind = 0; ind < n; ind++){ if(d[ind] > mx){ mx2 = mx; mx = d[ind]; } else if(d[ind] > mx2) mx2 = d[ind]; } ll lo = mx + mx2, hi = 2 * mx; vector<int> position(n); while(lo < hi){ ll D = (lo + hi) / 2; Data d1, d2; int cur = 0; // < 0 for(int i : perm2){ while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++; position[i] = cur; } init(); for(int j = 0; j < n; j++){ Data temp = get(position[j] - 1); d1.a = max(d1.a, temp.a + d[j] + c - p[j] - D); d1.b = min(d1.b, temp.b - d[j] - c - p[j] + D); d2.a = max(d2.a, temp.a + p[j] - D + d[j] + c); d2.b = min(d2.b, temp.b + p[j] + D - d[j] - c); add(where[j], Data(p[j] + d[j], p[j] - d[j])); } ll L1 = d1.a, R1 = d1.b; ll L2 = d2.a, R2 = d2.b; if(L1 > R1 || L2 > R2){ lo = D + 1; continue; } // some u, v with p[u] - p[v] in [L1, R1] and p[u] + p[v] in [L2, R2] bool ok = false; int ptr1 = 0; // first >= p[v] + L1 int ptr2 = n; // first >= L2 - p[v]; for(int v = 1; v < n; v++){ ll L = max(p[v] + L1, L2 - p[v]); ll R = min(p[v] + R1, R2 - p[v]); // in L, R? // int u = upper_bound(all(p), L - 1) - p.begin(); // first >= L while(ptr1 < n && p[ptr1] < L1 + p[v]) ptr1++; while(ptr2 > 0 && p[ptr2 - 1] >= L2 - p[v]) ptr2--; int u = max(ptr1, ptr2); if(u >= v) continue; if(p[u] > R) continue; ok = true; break; } if(ok) hi = D; else lo = D + 1; } return lo; } Data prefix[N]; ll p[N]; int perm1[N], perm2[N], where[N], position[N]; long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){ for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1]; iota(perm1, perm1 + n, 0); iota(perm2, perm2 + n, 0); sort(perm1, perm1 + n, [&](int i, int j){return d[i] - p[i] > d[j] - p[j];}); sort(perm2, perm2 + n, [&](int i, int j){return d[i] + p[i] < d[j] + p[j];}); for(int i = 0; i < n; i++) where[perm1[i]] = i; int mx = 0, mx2 = 0; for(int i = 1; i <= n; i++){ int ind = perm1[i - 1]; prefix[i] = prefix[i - 1]; merge(prefix[i], Data(p[ind] + d[ind], p[ind] - d[ind])); if(d[ind] > mx){ mx2 = mx; mx = d[ind]; } else if(d[ind] > mx2) mx2 = d[ind]; } ll lo = 2 * mx, hi = 1000000000LL * 10000000LL; while(lo < hi){ ll D = (lo + hi) / 2; Data d1, d2; int cur = 0; // < 0 for(int ind = 0; ind < n; ind++){ int i = perm2[ind]; while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++; position[i] = cur; } for(int j = 0; j < n; j++){ Data temp = prefix[position[j]]; d1.a = max(d1.a, temp.a + d[j] + c - p[j] - D); d1.b = min(d1.b, temp.b - d[j] - c - p[j] + D); d2.a = max(d2.a, temp.a + p[j] - D + d[j] + c); d2.b = min(d2.b, temp.b + p[j] + D - d[j] - c); } ll L1 = d1.a, R1 = d1.b; ll L2 = d2.a, R2 = d2.b; if(L1 > R1 || L2 > R2){ lo = D + 1; continue; } // some u, v with p[u] - p[v] in [L1, R1] and p[u] + p[v] in [L2, R2] bool ok = false; int ptr1 = 0; // first >= p[v] + L1 int ptr2 = n; // first >= L2 - p[v]; for(int v = 1; v < n; v++){ ll R = min(p[v] + R1, R2 - p[v]); // in L, R? // int u = upper_bound(all(p), L - 1) - p.begin(); // first >= L while(ptr1 < n && p[ptr1] < L1 + p[v]) ptr1++; while(ptr2 > 0 && p[ptr2 - 1] >= L2 - p[v]) ptr2--; int u = max(ptr1, ptr2); if(u >= v) continue; if(p[u] > R) continue; ok = true; break; } if(ok) hi = D; else lo = D + 1; } if(lo == 2 * mx){ return find_shortcut_old(n, l, d, c); } return lo; }

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut_old(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:98:16: warning: unused variable 'L' [-Wunused-variable]
   98 |             ll L = max(p[v] + L1, L2 - p[v]);
      |                ^
#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...