Submission #990537

#	Time	Username	Problem	Language	Result	Execution time	Memory
990537		AdamGS	Shortcut (IOI16_shortcut)	C++17	97 / 100	2021 ms	99456 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e6+7;
ll P[LIM], T[LIM], prefm[LIM], n, C;
ll tr[4*LIM], N=1;
vector<pair<ll,ll>>sum, roz;
void upd(int v, ll x) {
  v+=N;
  while(tr[v]<x) {
    tr[v]=x;
    v/=2;
  }
}
ll cnt(int x) {
  if(x<0) return -INF;
  x+=N;
  ll ans=tr[x];
  while(x>1) {
    if(x&1) ans=max(ans, tr[x-1]);
    x/=2;
  }
  return ans;
}
ll cnt(int l, int r) {
  if(l>r) return -INF;
  l+=N; r+=N;
  ll ans=max(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, tr[l+1]);
    if(r%2==1) ans=max(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
bool check(ll k) {
  rep(i, 2*N) tr[i]=-INF;
  tr[0]=INF;
  ll xpy_dol=-INF, xpy_gora=INF, ymx_dol=0, ymx_gora=INF;
  for(int b=1; b<n; ++b) {
    if(prefm[b-1]>k-P[b]-T[b]) {
      xpy_gora=min(xpy_gora, -prefm[b-1]+P[b]-T[b]+k-C);
      ymx_dol=max(ymx_dol, prefm[b-1]+P[b]+T[b]-k+C);
    }
  }
  int l=n-1;
  for(auto i : sum) {
    while(l>=0 && roz[l].st>k-i.st) {
      upd(roz[l].nd, P[roz[l].nd]+T[roz[l].nd]);
      --l;
    }
    ll x=cnt(0, i.nd-1);
    xpy_dol=max(xpy_dol, x+P[i.nd]+T[i.nd]-k+C);
    ymx_gora=min(ymx_gora, -x+P[i.nd]-T[i.nd]+k-C);
  }
  int la=n, lb=n-1, lc=-1, ld=0;
  rep(b, n) {
    while(la>0 && P[la-1]+P[b]>=xpy_dol) --la;
    while(lb>=0 && P[lb]+P[b]>xpy_gora) --lb;
    while(lc+1<n && P[b]-P[lc+1]>=ymx_dol) ++lc;
    while(ld<n && P[b]-P[ld]>ymx_gora) ++ld;
    if(la>lb || ld>lc) continue;
    int x=max(la, ld), y=min(lb, lc);
    y=min(y, b-1);
    if(x<=y) return true;
  }
  return false;
}
ll find_shortcut(int _n, vector<int>_l, vector<int>_d, int _c) {
  n=_n; C=_c;
  while(N<n) N*=2;
  rep(i, n-1) P[i+1]=P[i]+_l[i];
  rep(i, n) T[i]=_d[i];
  rep(i, n) {
    prefm[i]=T[i]-P[i];
    if(i) prefm[i]=max(prefm[i], prefm[i-1]);
    sum.pb({T[i]+P[i], i});
    roz.pb({T[i]-P[i], i});
  }
  sort(all(sum));
  sort(all(roz));
  ll po=0, ko=3000000000000000;
  while(po<ko) {
    ll sr=(po+ko)/2;
    if(check(sr)) ko=sr; else po=sr+1;
  }
  return po;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 0 / 3