| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1213786 | Nelt | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
#include "overtaking.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define T long long
#define U std::vector
#define P std::pair
#define S std::set
#define A std::array
#define M std::make_pair
#define B begin()
#define E end()
#define L lower_bound
#define O upper_bound
#define F for
#define W while
#define I if
#define R return
#define C const
#define Q queue
#define D dp
#define G mx
#define H tmp
#define K t
#define V v
#define X s
#define N n
#define Y m
#define Z x_
#define J INF
#define INF 9000000000000000000LL
T D[1005][1005], G[1005][1005], K[1005][1005], V[1005], X[1005], N, Y, Z;
P<T,T> H1[1005][1005];
U<P<T,T>> H[1005];
S<A<T,3>> R0;
#define GP(x) ([&]{auto it=R0.upper_bound({x,J,J});if(it!=R0.begin()){--it;if((*it)[1]>=x)R (*it)[2];}R -1;})()
#define ADD(l,r,z) ([&]{if(l>r)R;auto it=R0.lower_bound({l,-J,-J});while(it!=R0.end()&&(*it)[1]<=r)R0.erase(it++);if(it!=R0.end()&&(*it)[0]<=r){auto[a,b,c]=*it;R0.erase(it);R0.insert({r+1,b,c});}it=R0.lower_bound({l,-J,-J});if(it!=R0.begin()){--it;if((*it)[1]>=l){auto[a,b,c]=*it;R0.erase(it);R0.insert({a,l-1,c});if(b>=r)R0.insert({r+1,b,c});}}R0.insert({l,r,z});})()
#define INIT(L,N0,T0,W0,X0,M0,S0) ([&]{Z=X0;N=N0;Y=M0;F(T i=0;i<N;++i)K[i][0]=T0[i];F(T i=0;i<N;++i)V[i]=W0[i];V[N]=Z;F(T i=0;i<Y;++i)X[i]=S0[i];F(T i=0;i<N;++i)H[0].emplace_back(M(K[i][0],i));sort(H[0].B,H[0].E);F(T i=1;i<Y;++i){F(T x=0;x<N;++x){T j=H[i-1][x].second;K[j][i]=K[j][i-1]+V[j]*(X[i]-X[i-1]);H1[i][x]=std::max(x?H1[i][x-1]:M(0LL,0LL),M(K[j][i],j));T pos=L(H[i-1].B,H[i-1].E,M(K[j][i-1],-1LL))-H[i-1].B-1;if(pos>=0)K[j][i]=std::max(K[j][i],H1[i][pos].first);}F(T j=0;j<N;++j)H[i].emplace_back(M(K[j][i],j));sort(H[i].B,H[i].E);}for(T i=Y-1;~i;--i){F(T j=0;j<N;++j){T pt=GP(K[j][i]-X[i]*Z);if(pt==-1)D[i][j]=K[j][i]+(L-X[i])*Z;else{T last=K[j][i]+(X[pt-1]-X[i])*Z;T pos=L(H[pt-1].B,H[pt-1].E,M(last,-1LL))-H[pt-1].B-1;if(pos>=0)D[i][j]=D[pt][H1[pt][pos].second];else assert(0);}}if(i)F(T j=0;j<N;++j)ADD(K[j][i-1]-X[i-1]*Z+1,K[j][i]-X[i]*Z,i);}})()
#define ARR(x) ([&]{T pt=GP(x);if(pt==-1)R x+X[Y-1]*Z;T last=x+X[pt-1]*Z;T pos=L(H[pt-1].B,H[pt-1].E,M(last,-1LL))-H[pt-1].B-1;R D[pt][H1[pt][pos].second];})()
void init(int L, int N0, std::vector<long long> T0, std::vector<int> W0, int X0, int M0, std::vector<int> S0)
{
INIT(L, N0, T0, W0, X0, M0, S0);
}
long long arrival_time(long long cur)
{
return ARR(cur);
}