Submission #945308

#	Time	Username	Problem	Language	Result	Execution time	Memory
945308		Nhoksocqt1	Overtaking (IOI23_overtaking)	C++17	65 / 100	3575 ms	34284 KiB

overtaking

#ifndef Nhoksocqt1
    #include "overtaking.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> pli;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 1003;

pli sorted_timeTo[MAXN][MAXN];
ll maxPref[MAXN][MAXN], timeTo[MAXN][MAXN];
ll speed[MAXN], timeLeave[MAXN], pathLen, busnSpeed;
int staPos[MAXN];
int nArr, mArr;

ll sub1(ll Y) {
    if(busnSpeed >= speed[0] || Y <= timeLeave[0])
        return Y + pathLen * busnSpeed;

    for (int i = 1; i < mArr; ++i) {
        if(Y + busnSpeed * staPos[i] <= timeLeave[0] + speed[0] * staPos[i])
            return timeLeave[0] + speed[0] * staPos[i] + busnSpeed * (staPos[mArr - 1] - staPos[i]);
    }

    return Y + pathLen * busnSpeed;
}

ll sub2(ll Y) {
    ll res(Y + pathLen * busnSpeed);
    for (int i = 0; i < nArr; ++i) {
        if(timeLeave[i] < Y)
            res = max(res, timeLeave[i] + speed[i] * pathLen);
    }

    return res;
}

ll arrival_time(ll Y) {
    if(nArr == 1)
        return sub1(Y);

    if(mArr == 2)
        return sub2(Y);

    ll res(Y);
    for (int i = 1; i < mArr; ++i) {
        ll timeNow = res + (staPos[i] - staPos[i - 1]) * busnSpeed;
        int pos = lower_bound(sorted_timeTo[i - 1], sorted_timeTo[i - 1] + nArr, pli(res, -1)) - sorted_timeTo[i - 1] - 1;

        if(pos >= 0)
            timeNow = max(timeNow, maxPref[i - 1][pos]);

        res = timeNow;
    }

    return res;
}

void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S) {
    pathLen = _L, nArr = _N, mArr = _M, busnSpeed = _X;
    for (int i = 0; i < nArr; ++i)
        speed[i] = _W[i];

    for (int i = 0; i < nArr; ++i)
        timeLeave[i] = _T[i];

    for (int i = 0; i < mArr; ++i)
        staPos[i] = _S[i];

    for (int i = 0; i < nArr; ++i) {
        timeTo[0][i] = timeLeave[i];
        sorted_timeTo[0][i] = make_pair(timeTo[0][i], i);
    }

    sort(sorted_timeTo[0], sorted_timeTo[0] + nArr);
    for (int j = 1; j < mArr; ++j) {
        ll maxArrived(0);
        int k(0);
        for (int it = 0; it < nArr; ++it) {
            int i(sorted_timeTo[j - 1][it].se);
            while(k < nArr && sorted_timeTo[j - 1][k].fi < timeTo[j - 1][i]) {
                int x(sorted_timeTo[j - 1][k++].se);
                maxArrived = max(maxArrived, timeTo[j - 1][x] + (staPos[j] - staPos[j - 1]) * speed[x]);
            }

            timeTo[j][i] = max(maxArrived, timeTo[j - 1][i] + (staPos[j] - staPos[j - 1]) * speed[i]);
            sorted_timeTo[j][i] = make_pair(timeTo[j][i], i);
        }

        sort(sorted_timeTo[j], sorted_timeTo[j] + nArr);
    }

    for (int j = 0; j + 1 < mArr; ++j) {
        maxPref[j][0] = sorted_timeTo[j][0].fi + (staPos[j + 1] - staPos[j]) * speed[sorted_timeTo[j][0].se];
        for (int i = 1; i < nArr; ++i)
            maxPref[j][i] = max(maxPref[j][i - 1], sorted_timeTo[j][i].fi + (staPos[j + 1] - staPos[j]) * speed[sorted_timeTo[j][i].se]);
    }
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "overtaking"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<ll> _T;
    vector<int> _W, _S;
    int _L, _N, _M, _X;
    cin >> _L >> _N;

    _T.resize(_N);
    for (int i = 0; i < _N; ++i)
        cin >> _T[i];

    _W.resize(_N);
    for (int i = 0; i < _N; ++i)
        cin >> _W[i];

    cin >> _X >> _M;

    _S.resize(_M);
    for (int i = 0; i < _M; ++i)
        cin >> _S[i];

    init(_L, _N, _T, _W, _X, _M, _S);

    int _Q;
    cin >> _Q;
    for (int t = 0; t < _Q; ++t) {
        ll _Y;
        cin >> _Y;
        cout << "ASK " << _Y << ": ";
        cout << arrival_time(_Y) << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

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