Submission #1073654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073654		RecursiveCo	Overtaking (IOI23_overtaking)	C++17	65 / 100	3540 ms	26408 KiB

overtaking

// CF template, version 3.0

#include <bits/stdc++.h>
#include "overtaking.h"

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long int

template <typename T, typename I>
struct segtree {
    int n;
    vector<T> tree;
    vector<I> initial;
    T id;

    segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) {
        tree.resize(4 * n);
    }

    T conquer(T left, T right) {
        // write your conquer function
    }

    T value(I inp) {
        // write your value function
    }

    void build(int v, int l, int r) {
        if (l == r) tree[v] = value(initial[l]);
        else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int v, int l, int r, int i, I x) {
        if (l == r) tree[v] = value(x);
        else {
            int middle = (l + r) / 2;
            if (middle >= i) upd(2 * v, l, middle, i, x);
            else upd(2 * v + 1, middle + 1, r, i, x);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    T query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        else if (r < ql || qr < l) return id;
        int middle = (l + r) / 2;
        T left = query(2 * v, l, middle, ql, qr);
        T right = query(2 * v + 1, middle + 1, r, ql, qr);
        return conquer(left, right);
    }
};

// vector<int>

// L = length of the road
// N = number of buses (excl. reserve)
// T = times that the buses leave the beginning
// W = how long each bus takes to travel 1km
// X = how long the reserve takes to travel 1km
// M = number of stations
// S = locations of the stations (incl. 0 and L - 1)

vector<vector<pair<long long, int>>> dp;
vector<vector<long long>> prefmax;
int L;
int N;
vector<long long> T;
vector<int> W;
int X;
int M;
vector<int> S;

void init(int LI, int NI, vector<long long> TI, vector<int> WI, int XI, int MI, vector<int> SI) {
    L = LI;
    N = NI;
    T = TI;
    W = WI;
    X = XI;
    M = MI;
    S = SI;
    dp.resize(M, vector<pair<long long, int>>(N));
    prefmax.resize(M, vector<long long>(N));
    forto(N, i) dp[0][i] = {T[i], i};
    forto(M, i) {
        if (i == 0) continue;
        map<long long, vector<int>> lst;
        forto(N, j) lst[dp[i - 1][j].first].push_back(j);
        sortl(dp[i - 1]);
        long long maxi = -1ll;
        for (auto it = lst.begin(); it != lst.end(); it++) {
            long long here = -1ll;
            long long start = it->first;
            for (int j: it->second) {
                long long expected = start + (long long) (W[j]) * (long long) (S[i] - S[i - 1]);
                here = max(here, expected);
                dp[i][j].first = max(maxi, expected);
                dp[i][j].second = j;
            }
            maxi = max(maxi, here);
        }
        long long prefhere = -1ll;
        forto(N, j) {
            prefhere = max(prefhere, dp[i][dp[i - 1][j].second].first);
            prefmax[i - 1][j] = prefhere;
        }
    }
}

long long arrival_time(long long Y) {
    long long ans = Y;
    forto(M, i) {
        if (i == 0) continue;
        long long before = ans;
        long long expected = before + (long long) (X) * (long long) (S[i] - S[i - 1]);
        ans = max(ans, expected);
        int ind = lower_bound(dp[i - 1].begin(), dp[i - 1].end(), (pair<long long, int>) {before, -1}) - dp[i - 1].begin();
        if (ind--) {
            ans = max(ans, prefmax[i - 1][ind]);
        }
    }
    return ans;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
overtaking.cpp:100:5: note: in expansion of macro 'forto'
  100 |     forto(N, i) dp[0][i] = {T[i], i};
      |     ^~~~~
overtaking.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
overtaking.cpp:101:5: note: in expansion of macro 'forto'
  101 |     forto(M, i) {
      |     ^~~~~
overtaking.cpp:16:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
overtaking.cpp:104:9: note: in expansion of macro 'forto'
  104 |         forto(N, j) lst[dp[i - 1][j].first].push_back(j);
      |         ^~~~~
overtaking.cpp:16:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
overtaking.cpp:119:9: note: in expansion of macro 'forto'
  119 |         forto(N, j) {
      |         ^~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
overtaking.cpp:128:5: note: in expansion of macro 'forto'
  128 |     forto(M, i) {
      |     ^~~~~

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