Submission #1207902

#TimeUsernameProblemLanguageResultExecution timeMemory
1207902garam1732Shortcut (IOI16_shortcut)C++20
71 / 100
2056 ms10756 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 = 2e9; ll sum[MAXN], w[MAXN]; int N, C; vector<ll> v; int sz; struct MaxSeg { ll tree[MAXN*4]; void init() { fill(tree, tree+4*N, LLONG_MIN); } void update(int node, int s, int e, int idx, ll val) { if(idx < s || e < idx) return; if(s == e) { tree[node] = max(tree[node], val); return; } int mid = s+e>>1; update(node<<1, s, mid, idx, val); update(node<<1|1, mid+1, e, idx, val); tree[node] = max(tree[node<<1], tree[node<<1|1]); } ll solve(int node, int s, int e, int l, int r) { if(e < l || r < s) return LLONG_MIN; if(l <= s && e <= r) return tree[node]; int mid = s+e>>1; return max(solve(node<<1, s, mid, l, r), solve(node<<1|1, mid+1, e, l, r)); } } mxseg; struct MinSeg { ll tree[MAXN*4]; void init() { fill(tree, tree+4*N, LLONG_MAX); } void update(int node, int s, int e, int idx, ll val) { if(idx < s || e < idx) return; if(s == e) { tree[node] = min(tree[node], val); return; } int mid = s+e>>1; update(node<<1, s, mid, idx, val); update(node<<1|1, mid+1, e, idx, val); tree[node] = min(tree[node<<1], tree[node<<1|1]); } ll solve(int node, int s, int e, int l, int r) { if(e < l || r < s) return LLONG_MAX; if(l <= s && e <= r) return tree[node]; int mid = s+e>>1; return min(solve(node<<1, s, mid, l, r), solve(node<<1|1, mid+1, e, l, r)); } } mnseg; bool solve(ll L) { ll mnsum, mxsum, mndif, mxdif; mnsum = mndif = LLONG_MIN, mxsum = mxdif = LLONG_MAX; mxseg.init(); mnseg.init(); for(int i=N-2; i>=0; i--) { int it = lbd(v, sum[i+1]+w[i+1]); mxseg.update(1, 0, sz-1, it, sum[i+1]+w[i+1]); mnseg.update(1, 0, sz-1, it, sum[i+1]-w[i+1]); it = ubd(v, L+sum[i]-w[i]); ll mx = mxseg.solve(1, 0, sz-1, it, sz-1), mn = mnseg.solve(1, 0, sz-1, it, sz-1); if(mx != LLONG_MIN) { 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; i<N-1; i++) { ll mn = max(mnsum-sum[i], mndif+sum[i]); ll mx = min(mxsum-sum[i], mxdif+sum[i]); int it = lower_bound(sum+i+1, sum+N, mn)-sum; if(it < N && sum[it] <= 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(w[i]+sum[i]); sort(all(v)); comp(v); sz = v.size(); 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...