Submission #1079678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079678		MarwenElarbi	Overtaking (IOI23_overtaking)	C++17	19 / 100	10 ms	8536 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];
int n,m,x,e;
int 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 x){
  int l=-1;
  int r=n;
  while(r-l>1){
    int mid=(r+l)/2;
    if(timer[i][mid]<=x) 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,vector<long long>,greater<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});
      }
    }
    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: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35