#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;
int sz;
pll mx1 = {-INF, 0}, mx2 = {-INF, 0};
pll mn1[MAXN], mn2[MAXN];
bool solve(ll L) {
ll mnsum, mxsum, mndif, mxdif;
mnsum = mndif = -INF, mxsum = mxdif = INF;
for(int i=N-1; i>=0; i--) {
int it = lbd(v, pll(L+sum[i]-w[i]+1, 0));
ll mn = (mn1[it].ss == i ? mn2[it].ff : mn1[it].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]);
}
}//cout<<mnsum<<bl<<mxsum<<endl;
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(pll(w[i]+sum[i], i));
sort(all(v));
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]);
}
//for(int i=0; i<N; i++) cout<<mn1[i].ff<<bl;cout<<endl;
//solve(80); return 0;
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |