제출 #841484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841484		model_code	추월 (IOI23_overtaking)	C++17	100 / 100	3250 ms	77500 KiB

overtaking

// time_limit/sol_db_log2.cpp

#include "overtaking.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define lsb(x) (x) & (-x)
using namespace std;

const int maxN = 1001;
typedef long long ll;

int n, m, x, ord[maxN][maxN];
ll arrive[maxN][maxN], premax[maxN][maxN], mem[maxN][maxN];

vector <int> ind, w, s;
vector <ll> t, sortedT[maxN];

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n = N, m = M, x = X, t = sortedT[0] = T, w = W, s = S;

    vector <int> needed;
    for (int i = 0; i < N; ++i) {
        if (W[i] > x) {
            needed.push_back(i);
        }
    }
    n = N = needed.size();
    for (int i = 0; i < N; ++i) {
        W[i] = w[needed[i]];
        T[i] = t[needed[i]];
    }
    w = W, t = T;

    vector <int> inds;
    for (int i = 0; i < N; ++i) {
        arrive[0][i] = T[i];
        inds.push_back(i);
    }
    auto order_buses = [&](int j) {
        sort(all(inds), [&](int x, int y) {
            return arrive[j][x] < arrive[j][y];
        });
        for (int i = 0; i < N; ++i) {
            ord[j][i] = inds[i];
        }
    };
    for (int j = 1; j < M; ++j) {
        ll pre = 0, lpre = 0;
        order_buses(j - 1);
        for (int i = 0; i < N; ++i) {
            if (i && arrive[j - 1][inds[i]] != arrive[j - 1][inds[i - 1]]) {
                lpre = pre;
            }
            arrive[j][inds[i]] = max(arrive[j - 1][inds[i]] + 1ll * W[inds[i]] * (S[j] - S[j - 1]), lpre);
            premax[j][i] = pre = max(pre, arrive[j][inds[i]]);
            sortedT[j].push_back(arrive[j][inds[i]]);
        }
    }
    order_buses(M - 1);
    memset(mem, -1, sizeof mem);
}

ll calc(int j, ll y) {
    if (j == m - 1) {
        return y;
    }
    int index = lower_bound(all(sortedT[j]), y) - sortedT[j].begin();
    if (index < n && sortedT[j][index] == y && mem[j][index] != -1) {
        return mem[j][index];
    }
    auto countBelow = [](int j, ll curt) {
        int l = 0;
        int r = n;
        while (l < r) {
            int q = l + r >> 1;
            if (arrive[j][ord[j][q]] < curt) {
                l = q + 1;
            } else {
                r = q;
            }
        }
        return l;
    };
    int l = j + 1, r = m, below = countBelow(j, y);
    while (l < r) {
        int q = l + r >> 1, c = countBelow(q, y + 1ll * x * (s[q] - s[j]));
        if (c == below) {
            l = q + 1;
        } else {
            r = q;
        }
    }
    if (l == m) {
        return y + 1ll * x * (s[m - 1] - s[j]);
    }
    ll res = calc(l, premax[l][below - 1]);
    if (index < n && sortedT[j][index] == y) {
        mem[j][index] = res;
    }
    return res;
}

long long arrival_time(long long y)
{
    return calc(0, y);
}

컴파일 시 표준 에러 (stderr) 메시지

overtaking.cpp: In lambda function:
overtaking.cpp:76:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |             int q = l + r >> 1;
      |                     ~~^~~
overtaking.cpp: In function 'll calc(int, ll)':
overtaking.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int q = l + r >> 1, c = countBelow(q, y + 1ll * x * (s[q] - s[j]));
      |                 ~~^~~

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