Submission #955630

#	Time	Username	Problem	Language	Result	Execution time	Memory
955630		Prieved1	Overtaking (IOI23_overtaking)	C++17	39 / 100	3547 ms	16240 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_node {
	long long l, r;
	long long mx = 0;
	IST_node *left = nullptr, *right=nullptr;
	IST_node(long long _l, long long _r) {
		l = _l;
		r = _r;
	}
	void extend() {
		if(!left and l<r) {
			long long mid = (l+r)>>1;
			left = new IST_node(l, mid);
			right = new IST_node(mid+1, r);
		}
	}
	long long query(long long x) {
    if(l==r)return mx; 
    long long m=(l+r)/2;
    if(x<=m) {
      if(left==nullptr)return mx;
      return max(mx, left->query(x));
    }
    else {
      if(right==nullptr)return mx;
      return max(mx, right->query(x));
    }
	}
	void modify(long long L, long long R, long long val) {
    if(l > r)return;
    if(R < l or L > r)return;
		if(L <= l and r <= R) {
      mx=max(mx, val);
      return;
		}
		extend();
    right->modify(L, R, val);
    left->modify(L, R, val);
	}
};
class IST {
	private:
		IST_node *root;
	public:
		IST(long long n) {
			root = new IST_node(0,n);
		}
		long long query(long long x) {
			return max(x, root->query(x));
		}
		void modify(long long l, long long r, long long val) {
			root->modify(l, r, val);
		}
};
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.modify(idx[j], (long long)1e18+5, ta[i][j]);
//        cerr << idx[j] << ": " << ta[i][j] << " ";
      }
    }
//    cerr << endl;
  }
//  cerr << "A" << endl;
}
 
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: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35