제출 #1079687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079687		MarwenElarbi	추월 (IOI23_overtaking)	C++17	65 / 100	3542 ms	39948 KiB

overtaking

#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
const int nax=1e3+5;
long long timer[nax][nax];
long long segtree[nax][nax*4];
long long n,m,x,e;
long long tab[nax];
void update(int pos,int l,int r,int idx,long long value,int i){
  if(l==r){
    segtree[i][pos]=value;
    return;
  }
  int mid=(r+l)/2;
  if(idx<=mid) update(pos*2+1,l,mid,idx,value,i);
  else update(pos*2+2,mid+1,r,idx,value,i);
  segtree[i][pos]=max(segtree[i][pos*2+1],segtree[i][pos*2+2]);
  return;
}
long long query(int pos,int l,int r,int left,int right,int i){
  if(l>r||l>right||r<left) return -1;
  if(l>=left&&r<=right) return segtree[i][pos];
  int mid=(r+l)/2;
  return max(query(pos*2+1,l,mid,left,right,i),query(pos*2+2,mid+1,r,left,right,i));
}
int lower_bnd(int i,long long y){
  int l=-1;
  int r=n;
  while(r-l>1){
    int mid=(r+l)/2;
    if(timer[i][mid]<=y) l=mid;
    else r=mid;
  }
  return l;
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n=N,m=M,x=X,e=L;
    vector<pair<long long,long long>> lst;
    for (int i = 0; i < m; ++i) tab[i]=S[i];
    for (int i = 0; i < n; ++i) lst.pb({T[i],W[i]});
    for (int i = 0; i < m-1; ++i)
    {
      sort(lst.begin(),lst.end());
      for (int j = 0; j < n; ++j) timer[i][j]=lst[j].fi;
      priority_queue<long long> pq;
      lst.clear();
      for (int j = 0; j < n; ++j)
      {
        long long cur=max(lst[j].se*1ll*(S[i+1]-S[i])+lst[j].fi,1ll*(!pq.empty() ? pq.top() : -1));
        update(0,0,n-1,j,cur,i);
        lst.pb({cur,lst[j].se});
        pq.push(cur);
      }
    }
    return;
}

long long arrival_time(long long Y)
{
  for (int i = 0; i < m-1; ++i)
  {
    int cur=lower_bnd(i,Y-1);
    long long cnt=Y+1ll*x*(tab[i+1]-tab[i]);
    long long a=query(0,0,n-1,0,cur,i);
    Y=max(cnt,a);
  }
  return Y;
}

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