Submission #1010849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010849		mdn2002	Overtaking (IOI23_overtaking)	C++17	100 / 100	3011 ms	1734316 KiB

overtaking

/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

long long offset, last_offset;

struct Node {
    long long valuel = -1, valuer = -1, lazy = -1;
    int left = -1, right = -1;
    Node() {}
    Node(long long l, long long r) {
        valuel = l, valuer = r;
    }
};
Node st[53000001];
int cnt = 0;

void update(long long x, long long y, long long val, int node, long long l, long long r) {
    long long left = st[node].valuel + last_offset;
    long long right = st[node].valuer + last_offset;

    if (right < x || y < left) return;

    long long mid = (l + r) / 2;
    if(st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = (Node(l, mid));
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = (Node(mid + 1, r));
    }
    if (st[node].lazy != -1) {
        st[node].valuel = st[node].valuer = st[node].lazy;
        if (l != r) {
            int left = st[node].left, right = st[node].right;
            st[left].lazy = max(st[node].lazy, st[left].lazy);
            st[right].lazy = max(st[node].lazy, st[right].lazy);
        }
        st[node].lazy = -1;
    }

    if (x <= left && right <= y) {
        st[node].lazy = val - offset;
        st[node].valuel = st[node].valuer = st[node].lazy;
        if (l != r) {
            int left = st[node].left, right = st[node].right;
            st[left].lazy = max(st[node].lazy, st[left].lazy);
            st[right].lazy = max(st[node].lazy, st[right].lazy);
        }
        st[node].lazy = -1;
        return;
    }
    update(x, y, val, st[node].left, l, mid);
    update(x, y, val, st[node].right, mid +1, r);
    st[node].valuel = st[st[node].left].valuel;
    st[node].valuer = st[st[node].right].valuer;
}

long long get(long long l, long long r, int node , long long left, long long right) {
    long long mid = (left + right) / 2;
    if(st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = (Node(left, mid));
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = (Node(mid + 1, right));
    }
    if (st[node].lazy != -1) {
        st[node].valuel = st[node].valuer = st[node].lazy;
        if (left != right) {
            int left = st[node].left, right = st[node].right;
            st[left].lazy = max(st[node].lazy, st[left].lazy);
            st[right].lazy = max(st[node].lazy, st[right].lazy);
        }
        st[node].lazy = -1;
    }

    if (l <= left && right <= r) return st[node].valuel;
    if (l <= mid) return get(l, r, st[node].left, left, mid);
    return get(l, r, st[node].right, mid + 1, right);
}

int l, n, x, m;
vector<int> s;
vector<pair<long long, int>> buses;
vector<vector<pair<long long, int>>> times;
vector<vector<pair<long long, long long>>> max_times;
long long arrival_time(long long time) {
    long long val = get(time, time, 0, 0, 1e18 + 1);
    return val + offset;
}

void init(int L, int N, std::vector <long long> T, std::vector <int> W, int X, int M, std::vector <int> S) {
    st[0] = (Node(0, 1e18));
    l = L, n = N, x = X, m = M, s = S;
    for (int i = 0; i < N; i ++) {
        if (W[i] < X) continue;
        buses.push_back({T[i], W[i]});
    }
    n = buses.size();
    times.push_back(buses);

    vector<pair<long long, long long>> bb;
    max_times.push_back(bb);
    for (int i = 1; i < m; i ++) {
        sort(times[i - 1].begin(), times[i - 1].end());
        long long max_time = 0, delta_time = S[i] - S[i - 1];
        vector<pair<long long, int>> a;
        vector<pair<long long, long long>> b;

        for (int j = 0; j < n; j ++) {
            long long past_time = times[i - 1][j].first, speed = times[i - 1][j].second;
            long long time = past_time + speed * delta_time;
            max_time = max(max_time, time);
            a.push_back({max_time, speed});
            b.push_back({past_time, max_time});
        }
        times.push_back(a);
        max_times.push_back(b);
    }

    for (int i = 1; i < m; i ++) {
        long long delta_time = S[i] - S[i - 1];
        offset += delta_time * x;
        for (int j = n - 1; j >= 0; j --) {
            long long time = max_times[i][j].second, left = max_times[i][j].first + 1, right = time - x * delta_time;
            update(left, right, time, 0, 0, 1e18 + 1);
        }
        last_offset += delta_time * x;
    }
}

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