Submission #1207998

#TimeUsernameProblemLanguageResultExecution timeMemory
1207998garam1732Shortcut (IOI16_shortcut)C++20
100 / 100
1281 ms98416 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define bl ' ' #define endl '\n' #define all(v) (v).begin(), (v).end() #define comp(v) (v).erase(unique(all(v)), (v).end()) #define lbd(v,x) lower_bound(all(v), (x))-(v).begin() #define ubd(v,x) upper_bound(all(v), (x))-(v).begin() typedef long long ll; typedef pair<int, int> pi; typedef pair<pi, int> pii; typedef pair<int, pi> ipi; typedef pair<pi, pi> pipi; typedef pair<ll, ll> pll; const int MAXN = 100100*10; const ll MOD = 998244353; const ll INF = 1e16; ll sum[MAXN], w[MAXN]; int N, C; vector<pll> v, u; int sz; pll mx1 = {-INF, 0}, mx2 = {-INF, 0}; pll mn1[MAXN], mn2[MAXN]; int it[MAXN]; int l1[MAXN], r1[MAXN], l2[MAXN], r2[MAXN]; bool solve(ll L) { ll mnsum, mxsum, mndif, mxdif; mnsum = mndif = -INF, mxsum = mxdif = INF; for(int i=N-1, j=N; i>=0; i--) { while(j && v[j-1].ff > u[i].ff+L) j--; it[u[i].ss] = j; } for(int i=N-1; i>=0; i--) { int x = it[i]; ll mn = (mn1[x].ss == i ? mn2[x].ff : mn1[x].ff); ll mx = (mx1.ss == i ? mx2.ff : mx1.ff); if(mn != INF && mx > L+sum[i]-w[i]) { mn += L-w[i]-C; mx += -L+w[i]+C; mnsum = max(mnsum, sum[i]+mx); mxsum = min(mxsum, sum[i]+mn); mndif = max(mndif, mx-sum[i]); mxdif = min(mxdif, mn-sum[i]); } } for(int i=0, j=1; i<N-1; i++) { ll mn = max(mnsum-sum[i], mndif+sum[i]); ll mx = min(mxsum-sum[i], mxdif+sum[i]); if(j == i) j++; else if(j == N) j--; if(sum[j] >= mn) { while(j-1>i && sum[j-1] >= mn) j--; } else { while(j+1<N && sum[j+1] < mn) j++; j++; } if(j < N && sum[j] <= mx) return true; } return false; } long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { for(int i=1; i<n; i++) sum[i] = sum[i-1]+l[i-1]; for(int i=0; i<n; i++) w[i]=d[i]; N = n, C = c; for(int i=0; i<n; i++) v.push_back(pll(w[i]+sum[i], i)); for(int i=0; i<n; i++) u.push_back(pll(sum[i]-w[i], i)); sort(all(v)); sort(all(u)); for(int i=0; i<N; i++) { if(mx2.ff < sum[i]+w[i]) mx2 = pll(sum[i]+w[i], i); if(mx1 < mx2) swap(mx1, mx2); } mn1[N] = mn2[N] = pll(INF, 0); for(int i=N-1; i>=0; i--) { mn1[i] = mn1[i+1]; mn2[i] = mn2[i+1]; int x = v[i].ss; if(mn2[i].ff > sum[x]-w[x]) mn2[i] = pll(sum[x]-w[x], x); if(mn1[i] > mn2[i]) swap(mn1[i], mn2[i]); } ll lb = 0, ub = 1e16, mid; while(lb < ub) { mid = lb+ub>>1; if(solve(mid)) ub = mid; else lb = mid+1; } return lb; }

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...