Submission #990575

#	Time	Username	Problem	Language	Result	Execution time	Memory
990575		AdamGS	Shortcut (IOI16_shortcut)	C++17	31 / 100	2048 ms	4696 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], lewo[LIM], prawo[LIM], dlewo[LIM], dprawo[LIM], n, C;
ll sred(ll a, ll b) {
  ll sum=P[b]-P[a]+C; sum/=2;
  vector<pair<ll,ll>>S;
  ll akt=0;
  rep(i, b-a) {
    S.pb({T[a+i], akt});
    akt+=P[a+i+1]-P[a+i];
  }
  S.pb({prawo[b], akt});
  akt+=C;
  S[0].st=lewo[a];
  rep(i, b-a+1) S.pb({S[i].st, S[i].nd+akt});
  vector<pair<ll,ll>>X;
  int l=0, l2=0;
  ll ans=max(dlewo[a], dprawo[b]);
  rep(i, S.size()) {
    while(l<S.size() && S[l].nd-S[i].nd<=sum) {
      while(X.size() && X.back().st<=S[l].nd+S[l].st) X.pop_back();
      l2=min(l2, (int)X.size());
      X.pb({S[l].nd+S[l].st, l});
      ++l;
    }
    while(l2<X.size() && X[l2].nd<=i) ++l2;
    if(l2<X.size()) ans=max(ans, X[l2].st-S[i].nd+S[i].st);
  }
  return ans;
}
bool check(ll k) {
  ll xpy_gora=INF, ymx_dol=0;
  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);
    }
  }
  rep(b, n) rep(a, b) if(P[a]+P[b]<=xpy_gora && P[b]-P[a]>=ymx_dol) {
    if(sred(a, b)<=k) return true;
  }
  return false;
}
ll find_shortcut(int _n, vector<int>_l, vector<int>_d, int _c) {
  n=_n; C=_c;
  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]);
    if(i) lewo[i]=lewo[i-1]+P[i]-P[i-1];
    lewo[i]=max(lewo[i], T[i]);
    if(i) dlewo[i]=dlewo[i-1];
    dlewo[i]=max(dlewo[i], T[i]);
    if(i) dlewo[i]=max(dlewo[i], lewo[i-1]+P[i]-P[i-1]+T[i]);
  }
  for(int i=n-1; i>=0; --i) {
    if(i<n-1) prawo[i]=prawo[i+1]+P[i+1]-P[i];
    prawo[i]=max(prawo[i], T[i]);
    if(i<n-1) dprawo[i]=dprawo[i+1];
    dprawo[i]=max(dprawo[i], T[i]);
    if(i<n-1) dprawo[i]=max(dprawo[i], prawo[i+1]+P[i+1]-P[i]+T[i]);
  }
  ll po=0, ko=3000000000000000;
  while(po<ko) {
    ll sr=(po+ko)/2;
    if(check(sr)) ko=sr; else po=sr+1;
  }
  return po;
}

Compilation message (stderr)

shortcut.cpp: In function 'll sred(ll, ll)':
shortcut.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
shortcut.cpp:28:3: note: in expansion of macro 'rep'
   28 |   rep(i, S.size()) {
      |   ^~~
shortcut.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(l<S.size() && S[l].nd-S[i].nd<=sum) {
      |           ~^~~~~~~~~
shortcut.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(l2<X.size() && X[l2].nd<=i) ++l2;
      |           ~~^~~~~~~~~
shortcut.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(l2<X.size()) ans=max(ans, X[l2].st-S[i].nd+S[i].st);
      |        ~~^~~~~~~~~

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