Submission #900134

#	Time	Username	Problem	Language	Result	Execution time	Memory
900134		Nonoze	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	600 KiB

overtaking

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

vector<vector<pair<long long, long long>>> te;
vector<vector<long long>> prefix;
vector<int> s;
long long n, m, x, l;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    #define int long long

    l=L, n=N, m=M, x=X, s=S;
    te.clear();
    te.resize(m, vector<pair<int, int>>(n, {0, 0}));
    prefix.clear();
    prefix.resize(m, vector<int>(n, 0));
    for (int i=0; i<n; i++) te[0][i].first=T[i];
    for (int i=1; i<m; i++) {
        vector<pair<int, int>> temp;
        for (int j=0; j<n; j++) {
            te[i-1][j].second=te[i-1][j].first+W[j]*(s[i]-s[i-1]);
            temp.push_back({te[i-1][j].first, j});
        }
        sort(temp.begin(), temp.end());
        int mx=0;
        for (int j=0; j<n; j++) {
            mx=max(mx, te[i-1][temp[j].second].second);
            te[i][temp[j].second].first=mx;
        }
    }
    for (int i=0; i<m; i++) sort(te[i].begin(), te[i].end());
    return;
}

int lbb(int i, int act) {
    int left=0, right=n-1;
    int ans=-1;
    while (left<=right) {
        int mid=left+(right-left)/2;
        if (act>te[i][mid].first) {
            left=mid+1;
            ans=mid;
        } else {
            right=mid-1;
        }
    }
    return ans;
}

long long arrival_time(long long y)
{
    int act=y;
    for (int i=1; i<m; i++) {
        int lb=lbb(i-1, act);
        act=max(act+x*(s[i]-s[i-1]), (lb!=-1?te[i][lb].first:0));
    }
    return act;
}

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