제출 #955639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955639		Prieved1	추월 (IOI23_overtaking)	C++17	19 / 100	6 ms	4444 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=60;
  int ndcnt=1;
  long long RR=inf;
  long long T[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);
      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));
  }
  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)return -1;
    tmpval=max(tmpval, T[v]);
    if(max(r, tmpval) > x) {
      if(tmpval>x)return l;
      return x+1;
    }
    long long mid=(l+r)/2;
    long long ttt=get(x, tmpval, l, mid, L[v]);
    if(ttt!=-1)return ttt;
    return get(x, tmpval, mid+1, r, R[v]);
  }
};
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]);
//          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++) {
        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;
 
}

컴파일 시 표준 에러 (stderr) 메시지

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

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