Submission #1046963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046963		NeroZein	Overtaking (IOI23_overtaking)	C++17	65 / 100	3544 ms	39504 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std; 

int n, m;
vector<int> w, s;
vector<vector<long long>> t;
vector<vector<pair<long long, long long>>> ps;

void init(int L, int N_, vector<long long> T, vector<int> W, int X, int M_, vector<int> S) {
  n = N_, m = M_;
  w = W;
  w.push_back(X);
  s = S;
  t.resize(m);
  t[0] = T;
  for (int j = 1; j < m; ++j) {
    t[j].resize(n); 
    vector<long long> e(n);
    for (int i = 0; i < n; ++i) {
      e[i] = t[j - 1][i] + (long long) w[i] * (s[j] - s[j - 1]);
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0); 
    sort(ord.begin(), ord.end(), [&](int x, int y) {
      return t[j - 1][x] < t[j - 1][y];
    });
    int ptr = 0;
    long long mx = 0; 
    for (int i = 0; i < n; ++i) {
      int cur_bus = ord[i];
      while (ptr < i && t[j - 1][ord[ptr]] < t[j - 1][cur_bus]) {
        mx = max(mx, e[ord[ptr]]);
        ptr++; 
      }
      t[j][cur_bus] = max(e[cur_bus], mx); 
    }
    //cout << "J: " << j << ' ';
    //for (int i = 0; i < n; ++i) {
      //cout << t[j][i] << " \n"[i == n - 1];
    //}
  }
  ps.resize(m - 1);
  for (int j = 0; j < m - 1; ++j) {
    ps[j].resize(n);
    for (int i = 0; i < n; ++i) {
      ps[j][i] = {t[j][i], t[j + 1][i]};
    }
    sort(ps[j].begin(), ps[j].end()); 
    for (int i = 1; i < n; ++i) {
      ps[j][i].second = max(ps[j][i].second, ps[j][i - 1].second); 
    }
  }
}

long long arrival_time(long long cur_time) {
  for (int j = 1; j < m; ++j) {
    long long e = cur_time + (long long) w[n] * (s[j] - s[j - 1]);
    pair<long long, long long> key = {cur_time, 0LL};
    int ind = lower_bound(ps[j - 1].begin(), ps[j - 1].end(), key) - ps[j - 1].begin() - 1;
    long long block_time = 0;
    if (ind >= 0) {
      block_time = max(block_time, ps[j - 1][ind].second);
    }
    cur_time = max(e, block_time); 
  }
  return cur_time;
}

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