Submission #941194

#	Time	Username	Problem	Language	Result	Execution time	Memory
941194		WanWan	Overtaking (IOI23_overtaking)	C++17	65 / 100	3558 ms	26696 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 1005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int T[MAXN][MAXN];
int n;
int m;
int xt;
vector<int32_t>S;
vector<pi> nxt[MAXN]; // nxt[t] -> {time at this station, time at next station}
void init(int32_t L, int32_t n, std::vector<long long> tt, std::vector<int32_t> W, int32_t X, int32_t m, std::vector<int32_t> S)
{
    ::S=S;
    xt=X;
    ::n=n;
    ::m=m;
    // compute arrival times of each bus at each station
    for(int x=0;x<n;x++){
        T[x][0]=tt[x];
    }
    for(int t=1;t<m;t++){
        vector<pi> vec;
        for(int x=0;x<n;x++){
            vec.push_back({T[x][t-1],x});
        }
        sort(vec.begin(),vec.end());
        int idx=0;
        int mx=0;
        for(int x=0;x<n;x++){
            int xidx=vec[x].second;
            while(idx<n && vec[idx].first<T[xidx][t-1]){
                int idxidx=vec[idx].second;
                int exp=T[idxidx][t-1] + (int)W[idxidx] * (int)(S[t]-S[t-1]);
                mx=max(mx,exp);
                ++idx;
            }
            int ex=T[xidx][t-1] + (int)W[xidx] * (int)(S[t]-S[t-1]);
            T[xidx][t]=max(mx,ex);
        }
    }
    for(int t=0;t<m-1;t++){
        for(int x=0;x<n;x++){
            nxt[t].push_back({T[x][t],T[x][t+1]});
        }
        sort(nxt[t].begin(),nxt[t].end(),[](pi x, pi y){
            if(x.first != y.first)return x.first <y.first;
            else return x.second>y.second;//we only want to keep the biggest next of the same timing
        });
        bool need[n+5];memset(need,0,sizeof need);
        int mx=-oo;
        for(int x=0;x<n;x++){
            if(nxt[t][x].second > mx){
                mx=nxt[t][x].second;
                need[x]=1;
            }
        }
        vector<pi>res;
        for(int x=0;x<n;x++){
            if(need[x])res.push_back(nxt[t][x]);
        }
        nxt[t]=res;
    }

}

long long arrival_time(long long Y)
{

    for(int t=1;t<m;t++){
        int exp=Y + xt * (int)(S[t]-S[t-1]);
        auto it=lower_bound(nxt[t-1].begin(),nxt[t-1].end(),make_pair(Y,-oo));
        if(it != nxt[t-1].begin()){
            exp=max(exp,prev(it)->second);
        }
        Y=exp;
    }
    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