Submission #1066900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066900		mychecksedad	Overtaking (IOI23_overtaking)	C++17	19 / 100	7 ms	1884 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 3005;
const ll INF = 1e18;

set<pair<ll, ll>> pref[N];
vector<ll> T, W, S;
ll n, m, x, L;
set<array<ll, 3>> SE;
ll tots = 0;
void init(int Ll, int nn, std::vector<long long> t, std::vector<int> w, int xx, int mm, std::vector<int> s)
{ 
  L = Ll, n=nn, m=mm, x=xx;
  for(int i = 0; i < n; ++i){
    if(w[i] > x)
      W.pb(w[i]), T.pb(t[i]);
  }
  for(int f: s) S.pb(f);
  --m;

  n = W.size();

  vector<pair<ll, int>> F;
  for(int i =0; i < n; ++i) F.pb({W[i], i});
  sort(all(F));
  reverse(all(F));
  vector<vector<ll>> dp(n + 1, vector<ll>(m + 2));

  for(int i = 0; i < n; ++i){
    dp[i][0] = T[F[i].ss];
    for(int j = 1; j <= m; ++j){
      ll mx = dp[i][j - 1] + F[i].ff * (S[j] - S[j-1]);
      
      auto pos = pref[j].lower_bound(pair<ll,ll>{dp[i][j - 1], -1});
      if(pos == pref[j].begin()){
        dp[i][j] = mx;
      }else{
        pos = prev(pos);
        dp[i][j] = max(mx, (*pos).ss);
      }
      pref[j].insert({dp[i][j - 1], dp[i][j]});
    }
  }
  // for(int i = 1; i <= m; ++i){
  //   for(auto p: pref[i]) cout << p.ff << ' ' << p.ss << '\n';
  //     cout << '\n';
  // }
  // cout<<"c\n";
  vector<vector<array<ll, 3>>> ss(m + 1);
  for(int i = 1; i <= m; ++i){
    tots += S[i] - S[i - 1];
    for(auto p: pref[i]){
      p.ff++;
      if(p.ss - x * (S[i] - S[i - 1]) >= p.ff){
        ss[i].pb({p.ff - x * (tots - (S[i] - S[i-1])), p.ss - x * tots, p.ss + (L-tots) * x});
      }
    }
    sort(all(ss[i]));
    for(int j = int(ss[i].size()) - 2; j >= 0; --j){
      ss[i][j][1] = min(ss[i][j][1], ss[i][j + 1][0] - 1);
    }
    // cout << x * tots << '\n';
    // for(auto x: ss[i]){
    //   cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
    // }
    // cout << endl;
  }
  // cout << "good " << endl;
  SE.insert({-INF, INF, -1});
  for(int j = m; j >= 1; --j){
    for(auto p: ss[j]){
      ll l = p[0], r = p[1], to = p[2];
      if(r < l) continue;
      ll l2 = -1, r2 = -1;
      auto it = SE.lower_bound(array<ll,3>{l, -1, 0});
      while(it != SE.end() && (*it)[0] <= r){
        auto f = *it;
        auto it2 = next(it);
        // cout << f[1] << "wtf";
        if(f[1] >= r){
          if(f[2] != -1){
            to = max(to, f[2]);
          }else{
            if(it2 == SE.end()){
              // r + 1, inf, -1
              // r + 1, tooo, -1
              // cout << "wtf" << endl;
              l2 = r + 1;
              r2 = INF;
            }else{
              l2 = r + 1;
              r2 = (*it2)[0] - 1;
            }
          }
        }
        // cout << "wtf" << endl;
        SE.erase(it);
        it = SE.lower_bound(array<ll,3>{l, -1, 0});
      }
      if(l2 != -1) SE.insert({l2, r2, -1});
    //   for(auto x: SE){
    //   cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
    // }
    // cout << j << " phase " << l << ' ' << r << ' ' << to << endl;
      it = SE.lower_bound(array<ll,3>{l, -1, 0});
      if(it != SE.begin()){
        auto f = *prev(it);
        if(f[1] >= l){
          if(f[1] == r){
            to = max(to, f[2]);
          }
          SE.erase(prev(it));
          if(f[0] <= l - 1)
            SE.insert({f[0], l - 1, f[2]});
        }
      }
      SE.insert({l, r, to});
      if((*prev(SE.end()))[1] < INF){
        SE.insert({(*prev(SE.end()))[1] + 1, INF, -1});
      }
    //    for(auto x: SE){
    //   cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
    // }
    // cout << j << " phase " << l << ' ' << r << ' ' << to  << endl;
    // cout << '\n';
    }
   
  }


  return;
}

long long arrival_time(long long Y)
{
  // ll cur = Y;
  // for(int j = 1; j <= m; ++j){
  //   ll mx = cur + x * (S[j] - S[j-1]);
  //   auto pos = pref[j].lower_bound(pair<ll,ll>{cur, -1});
  //   if(pos == pref[j].begin()){
  //     cur = mx;
  //   }else{
  //     pos = prev(pos);
  //     cur = max(mx, (*pos).ss);
  //   }
  // }
  auto it = SE.lower_bound(array<ll,3>{Y, INF+1, INF});
  --it;
  if((*it)[2] == -1) return Y + x * L;
  return (*it)[2];
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35