Submission #1010777

#TimeUsernameProblemLanguageResultExecution timeMemory
1010777mdn2002Overtaking (IOI23_overtaking)C++17
Compilation error
0 ms0 KiB
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

long long offset, last_offset;

struct SegmentTree {
    struct Node {
        long long valuel = -1, valuer = -1, lazy = -1e17;
        long long left = -1, right = -1, lx, rx, len, mid;
        Node(long long a, long long b) {
            lx = a, rx = b;
            len = rx - lx + 1;
            mid = (lx + rx) / 2;
        }
    };

    vector<Node> st;
    SegmentTree(long long sz) {
        st.clear();
        st.push_back(Node(0, sz - 1));
    }

    void create(int node) {
        if(st[node].left == -1) {
            st[node].left = st.size();
            st.push_back(Node(st[node].lx, st[node].mid));
            st[node].right = st.size();
            st.push_back(Node(st[node].mid + 1, st[node].rx));
        }
    }

    void push(int node, long long l, long long r) {
        if (st[node].lazy == -1e17) return;
        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 = -1e17;
    }
    void update(long long x, long long y, long long val, int node = 0) {
        long long l = st[node].lx, r = st[node].rx;
        if (l != r) create(node);
        push(node, l, r);

        long long left = st[node].valuel + last_offset;
        if (st[node].valuel == -1) left = l + last_offset;
        long long right = st[node].valuer + last_offset;
        if (st[node].valuer == -1) right = r + last_offset;

        if (right < x || y < left) return;
        if (x <= left && right <= y) {
            st[node].lazy = val - offset;
            push(node, l, r);
            return;
        }
        update(x, y, val, st[node].left);
        update(x, y, val, st[node].right);
        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 = 0) {
        long long left = st[node].lx, right = st[node].rx;
        if (left != right) create(node);
        push(node, left, right);
        if (l <= st[node].lx && st[node].rx <= r) return st[node].valuel;
        if (l <= st[node].mid) return get(l, r, st[node].left);
        return get(l, r, st[node].right);
    }
};

SegmentTree seg(1e18 + 1);
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 = seg.get(time, time), ans = val + offset;
    if (val == -1) ans = time + offset;
    return ans;
}

void init(int L, int N, std::vector <long long> T, std::vector <int> W, int X, int M, std::vector <int> S) {
    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 delta_time = S[i] - S[i - 1], time = max_times[i][j].second, left = max_times[i][j].first + 1, right = time - x * delta_time;
            seg.update(left, right, time);
        }
        last_offset += delta_time * x;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    while (T --){
        int L, N, X, M;
        cin >> L >> N;
        vector<long long> T(N);
        vector<int> W(N);
        for (int i = 0; i < N; i ++) cin >> T[i];
            for (int i = 0; i < N; i ++) cin >> W[i];
            cin >> X >> M;
        vector<int> S(M);
        for (int i = 0; i < M; i ++) cin >> S[i];
        init(L, N, T, W, X, M, S);

        cout << arrival_time(0) << endl;
        cout << arrival_time(50) << endl;
    }
}
/*
6 4
20 10 40 0
5 20 20 30
10 4
0 1 3 6
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccth5VWl.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccatSr8m.o:overtaking.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status