Submission #843794

#	Time	Username	Problem	Language	Result	Execution time	Memory
843794		bachhoangxuan	Overtaking (IOI23_overtaking)	C++17	100 / 100	1643 ms	147368 KiB

overtaking

#include "overtaking.h"

#include<bits/stdc++.h>
using namespace std;
const long long inf=LLONG_MAX;
const int maxn=1e3+5;
#define pii pair<int,int>
#define fi first
#define se second

struct bus{
    long long s,t;
    int id;
    bool operator<(bus o){
        if(s!=o.s) return s<o.s;
        else return t<o.t;
    }
};

int M,N;
long long X,L;
vector<long long> T,S,W;

bus B[maxn][maxn];
long long res[maxn][maxn];

namespace Segtree{
    int n;
    vector<pii> tree;
    vector<long long> com;
    void add(long long x){
        com.push_back(x);
    }
    void build(){
        sort(com.begin(),com.end());
        com.erase(unique(com.begin(),com.end()),com.end());
        n=(int)com.size();
        tree.assign(4*n,make_pair(M,0));
    }
    void update(int l,int r,int id,int tl,int tr,pii x){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr) return tree[id]=min(tree[id],x),void();
        int mid=(l+r)>>1;
        update(l,mid,id<<1,tl,tr,x);update(mid+1,r,id<<1|1,tl,tr,x);
    }
    void update(long long l,long long r,pii x){
        if(l>r) return;
        int pl=upper_bound(com.begin(),com.end(),l)-com.begin();
        int pr=upper_bound(com.begin(),com.end(),r)-com.begin();
        update(1,n,1,pl,pr,x);
    }
    pii query(int l,int r,int id,int x){
        if(l==r) return tree[id];
        int mid=(l+r)>>1;
        pii res=tree[id];
        if(x<=mid) res=min(res,query(l,mid,id<<1,x));
        else res=min(res,query(mid+1,r,id<<1|1,x));
        return res;
    }
    pii query(long long x){
        int px=upper_bound(com.begin(),com.end(),x)-com.begin();
        return query(1,n,1,px);
    }
}

void init(int l, int n, vector<long long> st, vector<int> w, int x, int m, vector<int> s)
{
    L=l;N=n;X=x;M=m;T=st;
    W.resize(N);S.resize(M);
    for(int i=0;i<N;i++) W[i]=w[i];
    for(int i=0;i<M;i++) S[i]=s[i];

    for(int i=0;i<N;i++) B[0][i]={0,T[i],i};
    for(int i=1;i<M;i++){
        for(int j=0;j<N;j++){
            auto [ss,tt,id]=B[i-1][j];
            B[i][j]={tt,tt+(S[i]-S[i-1])*W[id],id};
        }
        sort(B[i],B[i]+N);
        for(int j=1;j<N;j++) B[i][j].t=max(B[i][j].t,B[i][j-1].t);
        for(int j=0;j<N;j++){
            Segtree::add(B[i][j].s-X*S[i-1]+1);
            Segtree::add(B[i][j].t-X*S[i]);
        }
    }
    Segtree::add(-inf);
    Segtree::build();
    for(int i=M-1;i>=1;i--){
        for(int j=0;j<N;j++){
            pii pos=Segtree::query(B[i][j].t-X*S[i]);pos.se=-pos.se;
            if(pos.fi==M) res[i][j]=B[i][j].t+X*(L-S[i]);
            else res[i][j]=res[pos.fi][pos.se];
            //cout << res[i][j] << ' ';
        }
        for(int j=0;j<N;j++) Segtree::update(B[i][j].s-X*S[i-1]+1,B[i][j].t-X*S[i]-1,{i,-j});
        //cout << '\n';
    }
}

long long arrival_time(long long cur)
{
    pii pos=Segtree::query(cur);pos.se=-pos.se;
    //cout << pos.fi << ' ' << pos.se << ' ' << B[pos.fi][pos.se].id << '\n';
    if(pos.fi==M) return cur+X*L;
    else return res[pos.fi][pos.se];
}

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