Submission #955645

#	Time	Username	Problem	Language	Result	Execution time	Memory
955645		Prieved1	Overtaking (IOI23_overtaking)	C++17	100 / 100	3415 ms	515188 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long speed;
const long long inf=1e18+10;
vector<vector<long long>> ta;
vector<vector<pair<long long, long long>>> pr;
long long asdf=0;
namespace ST {
  static const long long NN=1e6;
  static const int LG=30;
  int ndcnt=1;
  long long RR=inf;
  long long T[NN*LG], T2[NN*LG];
  long long L[NN*LG], R[NN*LG];
  void update1(long long ll, long long rr, long long val, long long l=0, long long r=0, long long v=1) {
    if(r<ll or rr<l)return;
    if(ll<=l and r<=rr) {
      T[v]=max(T[v], val);
      T2[v]=max(T2[v], T[v]);
      return;
    }
    long long mid=(l+r)/2;
    if(L[v]==0)L[v]=++ndcnt;
    if(R[v]==0)R[v]=++ndcnt;
    update1(ll, rr, val, l, mid, L[v]);
    update1(ll, rr, val, mid+1, r, R[v]);
    T2[v]=max(T2[v], max(T2[L[v]], T2[R[v]]));
  }
  long long query1(long long x, long long l, long long r, long long v) {
    if(v==0)return 0;
    long long mid=(l+r)/2;
    if(x <= mid) {
      return max(T[v], query1(x, l, mid, L[v]));
    }
    else return max(T[v], query1(x, mid+1, r, R[v]));
  }
  void update(long long l, long long r, long long val) {
    update1(l, r, val, 0, RR, 1);
  }
  long long query(long long x) {
    return max(x, query1(x, 0, RR, 1));
  }
  long long get(long long x, long long tmpval = 0, long long l=0, long long r=RR, long long v=1){
    if(v==0) {
      if(tmpval>x)return l;
      if(r>x)return x+1;
      return -1;
    }
    tmpval=max(tmpval, T[v]);
    long long mid=(l+r)/2;
    if(max(mid, max(tmpval, T2[L[v]]))>x)return get(x, tmpval, l, mid, L[v]);
    long long ttt=get(x, tmpval, mid+1, r, R[v]);
    if(ttt!=-1) {
      return ttt;
    }
    if(max(r, tmpval) > x) {
      if(tmpval>x)return l;
      return x+1;
    }
    return -1;
  }
};
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
  speed=X;
  asdf=S.back()*speed;
  ta=vector<vector<long long>> (M, vector<long long> (N));
  for(int i = 0;i<M;i++) {
    for(int j = 0;j<N;j++) {
      if(i==0)ta[i][j]=T[j];
      else ta[i][j]=ta[i-1][j]+(long long)(S[i]-S[i-1])*W[j];
    }
    if(i){
      vector<pair<pair<long long, long long>, int>> idxx;
      for(int j = 0;j<N;j++) {
        idxx.push_back({{ta[i-1][j], ta[i][j]}, j});
      }
      sort(idxx.begin(), idxx.end());
      for(int k = 1;k<N;k++) {
        ta[i][idxx[k].second]=max(ta[i][idxx[k].second], ta[i][idxx[k-1].second]);
      }
    }
  }
  pr.resize(M);
  for(int i = 0 ;i<M;i++) {
    vector<long long> idx;
    for(int j = 0;j<N;j++) {
        ta[i][j]-=S[i]*speed;
    }
    if(i) {
      for(int j = 0;j<N;j++) {
          long long lo = 0, hi = inf;
          long long LL=ST::get(ta[i-1][j]);
          idx.push_back(LL);
      }
      for(int j = 0;j<N;j++) {
        if(idx[j]==-1)continue;
        ST::update(idx[j], (long long)inf, ta[i][j]);
      }
    }
  }
}
 
long long arrival_time(long long Y) {
  long long ans=ST::query(Y);
  return ans+asdf;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:95:21: warning: unused variable 'lo' [-Wunused-variable]
   95 |           long long lo = 0, hi = inf;
      |                     ^~
overtaking.cpp:95:29: warning: unused variable 'hi' [-Wunused-variable]
   95 |           long long lo = 0, hi = inf;
      |                             ^~

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