Submission #1061069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061069		fuad27	Overtaking (IOI23_overtaking)	C++17	100 / 100	2986 ms	515108 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:25: warning: unused variable 'lo' [-Wunused-variable]
   95 |               long long lo = 0, hi = inf;
      |                         ^~
overtaking.cpp:95:33: 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