| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 600911 | balbit | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 我的心裡只有你沒有他
#pragma GCC optimize("O3", "unroll-loops")
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair <int, int >
#define f first
#define s second
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif // BALBIT
#define pb push_back
#define REP(i,n) for (int i = 0; i<(n); ++i)
#define REP1(i,n) for (int i = 1; i<=(n); ++i)
const int maxn = 1e6+5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int P[maxn], D[maxn]; // position, depth
vector<pii> Aval, Bval; // A is Da + Pa, B is Db - Pb
ll C[2][2], bigB[2], sbigB[2], whoB[2];
double t1=0,t2=0;
bool okay(int n, ll M, ll cost) {
// for all D[a] + P[a] - D[b] + P[b] >= M,
clock_t t = clock();
bug(M, cost);
REP(r,2) REP(R, 2) {
C[r][R] = -inf;
bigB[r] = sbigB[r] = -inf;
whoB[r] = -1;
}
int j = SZ(Bval)-1;
if (M < 1e9 * 2+10) {
REP(i,SZ(Aval)) {
int a = Aval[i].s;
while (j>=0 && Aval[i].f+Bval[j].f > M) {
// work j
int b = Bval[j].s;
bug(a,b,Aval[i].f + Bval[i].f);
REP(vx,2) {
ll val = D[b] +(vx?-1:1)*P[b];
if (val > bigB[vx]) {
sbigB[vx] = bigB[vx];
whoB[vx] = b;
bigB[vx] = val;
}else if (val > sbigB[vx]) {
sbigB[vx] = val;
}
}
--j;
}
REP(vx,2) {
ll ka = cost-M+D[a]+(vx?-P[a]:P[a]);
REP(vy,2) {
int bval = whoB[vy]==a?sbigB[vy] : bigB[vy];
MX(C[vx][vy], (ka + bval));
}
}
if (C[0][0] > -C[1][1]) return 0;
if (C[0][1] > -C[1][0]) return 0;
}
}else{
REP(i,SZ(Aval)) {
int a = Aval[i].s;
while (j>=0 && Aval[i].f+Bval[j].f > M) {
int b = Bval[j].s;
REP(vx,2) {
MX(bigB[vx], D[b] +(vx?-P[b]:P[b]));
}
--j;
}
REP(vx,2) {
ll ka = cost-M+D[a]+(vx?-P[a]:P[a]);
REP(vy,2) {
MX(C[vx][vy], (ka + bigB[vy]));
}
}
if (C[0][0] > -C[1][1]) return 0;
if (C[0][1] > -C[1][0]) return 0;
}
}
t1 += (clock()-t) / (double)CLOCKS_PER_SEC;
t = clock();
// REP(X,2) REP(Y,2) C[X][Y] += cost-M;
// bug(C[0][0], C[0][1], C[1][0], C[1][1]);
vector<ll> ya;
signed i00=n, i01=-1, i10=0,i11=n-1;
t = clock();
bool ok = 0;
REP(a, n) {
ll X = P[a];
if (C[0][0] - X >= C[1][0] + X) {
while (i00-1>=0 && P[i00-1] >= C[0][0]-X) --i00;
}else{
while (i00<n && P[i00] < C[1][0] + X) ++ i00;
}
if (-C[0][1] + X <= -C[1][1] - X) {
while (i01+1 <n && P[i01+1] <= -C[0][1] + X) ++i01;
}else{
while (i01 >= 0 && P[i01] > -C[1][1] - X) --i01;
}
if (i00 <= i01) {
ok = 1; break;
}
}
t2 += (clock()-t) / (double)CLOCKS_PER_SEC;
return ok;
// conditions: Pa + Da +
}
long long find_shortcut(signed n, std::vector<signed> l, std::vector<signed> _d, signed _c)
{
// watermelon 4A orz
bug(1,2);
P[0] = 0;
REP(i,n-1) P[i+1] = P[i] + l[i];
// P[n] = inf*2;
REP(i,n) D[i] = _d[i];
REP(i,n) {
Aval.pb({D[i] + P[i], i});
Bval.pb({D[i] - P[i], i});
}
sort(ALL(Aval));
sort(ALL(Bval));
int lb=P[n-1]/3, rb=P[n-1]+2e9+100;
while (lb != rb) {
ll M = (lb+rb)/2;
if (okay(n,M,_c)) {
rb = M;
}else {
lb = M+1;
}
}
bug(lb);
return lb;
}
/*
4 10
10 20 20
0 40 0 30
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
3 10
1 1
0 1000 0
*/
//
signed main(){
// bug(hi);
int n; cin>>n;
REP(www, 1) {
vector<signed> l, d;
REP(i,n-1) {
l.pb(rand()%1000000000);
}
REP(i,n) {
d.pb(rand()%1000000000);
}
bug(find_shortcut(n, l, d, 222));
bug(t1,t2);
}
}