Submission #1131593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131593		79brue	Overtaking (IOI23_overtaking)	C++20	19 / 100	4 ms	4424 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k; ll L, base_speed;
ll start[1002], speed[1002], arr[1002];

map<ll, ll> mp;
ll stop[1002][1002];

void init(int _L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
    L = _L, base_speed = X;
    for(int i=0; i<N; i++){
        if(W[i] <= X) continue;
        ++n;
        start[n] = T[i], speed[n] = W[i] - X;
    }

    k = M;
    for(int i=1; i<=k; i++) arr[i] = S[i-1];

    vector<int> order;
    for(int i=1; i<=n; i++) order.push_back(i);
    sort(order.begin(), order.end(), [&](int a, int b){
        return speed[a] > speed[b];
    });

    for(int i=1; i<=n; i++) stop[1][i] = start[i];
    for(int d=2; d<=k; d++){
        map<ll, ll> mp;
        for(int x: order){
            ll v = stop[d-1][x] + (arr[d] - arr[d-1]) * speed[x];
            auto it = mp.lower_bound(stop[d-1][x]);
            if(it != mp.begin()) v = max(v, prev(it)->second);
            stop[d][x] = v;

            if(mp.count(stop[d-1][x]) == 0 || mp[stop[d-1][x]] < stop[d][x]) mp.insert(make_pair(stop[d-1][x], stop[d][x]));
        }
    }

    mp[-1] = -1;
    mp[ll(4e18)] = ll(4e18);
    for(int d=k; d>=2; d--){
        vector<pair<ll, ll> > vec;
        for(int i=1; i<=n; i++) vec.push_back(make_pair(stop[d-1][i], stop[d][i]));
        sort(vec.begin(), vec.end());
        for(int i=0; i<(int)vec.size(); i++){
            if(i && vec[i-1].first == vec[i].first) continue;
            ll x = vec[i].first, y = vec[i].second;
            auto it = mp.lower_bound(x);
            ll yv = max(y, prev(mp.lower_bound(y))->second);
            while(it->second <= yv){
                ++it;
                mp.erase(prev(it));
            }
            mp[x] = max(mp[x], yv);
        }

//        printf("d = %d\n", d);
//        for(auto [x, y]: mp) printf("(%lld, %lld) ", x, y);
//        puts("");
    }
}

ll arrival_time(ll Y){
    ll yv = max(Y, prev(mp.lower_bound(Y))->second);
    return yv + L * base_speed;
}

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