Submission #1079028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079028		becaido	Overtaking (IOI23_overtaking)	C++17	100 / 100	715 ms	59336 KiB

overtaking

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "overtaking.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1005;

int n, m, x;
int a[SIZE], w[SIZE];
ll t[SIZE][SIZE], ans[SIZE][SIZE];

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> _S) {
    n = N, m = M, x = X;
    FOR (i, 1, m) a[i] = _S[i - 1];
    int sz = 0;
    FOR (i, 1, n) if (W[i - 1] > X) {
        sz++;
        t[1][sz] = T[i - 1];
        w[sz] = W[i - 1];
    }
    n = sz;
    FOR (i, 2, m) {
        vector<int> id(n + 1);
        iota(id.begin(), id.end(), 0);
        sort(id.begin() + 1, id.end(), [&](int x, int y) {
            return t[i - 1][x] < t[i - 1][y];
        });
        ll mx = 0;
        FOR (l, 1, n) {
            int r = l;
            while (r < n && t[i - 1][id[l]] == t[i - 1][id[r + 1]]) r++;
            FOR (j, l, r) t[i][id[j]] = max(mx, t[i - 1][id[j]] + 1ll * (a[i] - a[i - 1]) * w[id[j]]);
            FOR (j, l, r) mx = max(mx, t[i][id[j]]);
            l = r;
        }
    }
    FOR (i, 1, m) {
        sort(t[i] + 1, t[i] + n + 1);
        fill(ans[i] + 1, ans[i] + n + 1, -1);
    }
}

ll cal(int i, ll Y) {
    if (i == m) return Y;
    int j = lower_bound(t[i] + 1, t[i] + n + 1, Y) - t[i] - 1;
    if (j == 0) return Y + 1ll * x * (a[m] - a[i]);
    if (j < n && Y == t[i][j + 1] && ans[i][j + 1] != -1) return ans[i][j + 1];
    int l = i + 1, r = m + 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (t[mid][j] >= Y + 1ll * x * (a[mid] - a[i])) r = mid;
        else l = mid + 1;
    }
    ll res = (l == m + 1 ? Y + 1ll * x * (a[m] - a[i]) : cal(l, t[l][j]));
    if (j < n && Y == t[i][j + 1]) ans[i][j + 1] = res;
    return res;
}

ll arrival_time(ll Y) {
    return cal(1, Y);
}

/*
in1
6 4 10 4 2
20 10 40 0
5 20 20 30
0 1 3 6
0
50
out1
60
130
*/

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