Submission #1076081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076081		anango	Overtaking (IOI23_overtaking)	C++17	65 / 100	3573 ms	34312 KiB

overtaking

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

int n,m;
int x;
int l;
vector<int> s; // where the sorting stations are
vector<int> t; // leaving times
vector<int> w; //speeds

vector<vector<int>> ET; //expected time
vector<vector<int>> sorted_by_i; //ETs, sorted by the ith station
vector<vector<int>> sorted_by_minus_one; //ETs, sorted by the previous station
vector<vector<int>> prefmax;  //prefix maximums of sorted by minus one

void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S) {
    s=vector<int>(S.begin(),S.end());
    t=T;
    w=vector<int>(W.begin(),W.end());
    n=N;
    l=L;
    m=M;
    x=X;

    ET=sorted_by_i=sorted_by_minus_one=vector<vector<int>>(M,vector<int>(N,0)); //the ET of each bus at each sorting station
    prefmax=vector<vector<int>>(m,vector<int>(n+1,0));
    for (int i=0; i<N; i++) {
        ET[0][i] = t[i];
        sorted_by_i[0][i] = i;
    }
    for (int j=1; j<m; j++) {
        int delta = s[j]-s[j-1];
        for (int i=0; i<n; i++) {
            ET[j][i] = ET[j-1][i]+w[i]*delta;
        }
        for (int i=0; i<n; i++) {
            for (int i1=0; i1<n; i1++) {
                if (ET[j-1][i]>ET[j-1][i1]) {
                    ET[j][i] = max(ET[j][i],ET[j][i1]);
                }
            }
        }
    }
    for (int j=0; j<m; j++) {
        for (int i=0; i<n; i++) {
            sorted_by_i[j][i] = sorted_by_minus_one[j][i] = i;
        }
    }
    for (int j=0; j<m; j++) {
        sort(sorted_by_i[j].begin(), sorted_by_i[j].end(),[&](const int i1, const int i2) {
            return ET[j][i1]<ET[j][i2];
        });
        if (j>0) {
            sort(sorted_by_minus_one[j].begin(), sorted_by_minus_one[j].end(),[&](const int i1, const int i2) {
                return ET[j-1][i1]<ET[j-1][i2];
            });
        }
    }
    for (int j=1; j<m; j++) {
        int ma = 0;
        for (int i=0; i<n; i++) {
            prefmax[j][i] = ma;
            ma=max(ma,ET[j][sorted_by_minus_one[j][i]]);
        }
        prefmax[j][n] = ma;
    }
    return;
}

long long arrival_time(long long Y) {
    for (int j=1; j<m; j++) {
        int delta = s[j]-s[j-1];
        int prevy = Y;
        Y+=delta*x;
        //cout << j <<" " << delta <<" " << x << " " << Y << endl;
        int l = 0;
        int r = n;
        while (l<r) {
            int m = (l+r)/2;
            int val = ET[j-1][sorted_by_minus_one[j][m]];
            if (val<prevy) {
                //need higher val
                l=m+1;
            }
            else {
                //need lower val
                r=m;
            }
        }
        //this is the number of values that matter, plus 1
        int maval = prefmax[j][l];
        Y=max(Y,maval);

    }
    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