제출 #955634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955634		Prieved1	추월 (IOI23_overtaking)	C++17	19 / 100	56 ms	6656 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;

struct IST {
  static const long long NN=2e3;
  static const int LG=64;
  int ndcnt=1;
  long long RR;
  long long T[NN*LG];
  long long L[NN*LG], R[NN*LG];
  IST(long long _R) {
    RR=_R;
  }
  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);
      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]);
  }
  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));
  }
};
IST st((long long)inf+10);

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=inf;
          while(lo <= hi) {
            long long mid=(lo+hi)/2;
            if(st.query(mid) > ta[i-1][j]) {
              hi=mid-1;
              LL=mid;
            }
            else {
              lo=mid+1;
            }
          }
          idx.push_back(LL);
      }
      for(int j = 0;j<N;j++) {
        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;
 
}

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