Submission #1147251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147251		FZ_Laabidi	Infinite Race (EGOI24_infiniterace2)	C++20	0 / 100	0 ms	328 KiB

Main

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

struct FenwickTree {
    vector<int> bit;
    int n;

    FenwickTree(int size) {
        n = size;
        bit.assign(n + 1, 0);
    }

    void add(int index, int value) {
        for (; index <= n; index += index & -index)
            bit[index] += value;
    }

    int sum(int index) {
        int result = 0;
        for (; index > 0; index -= index & -index)
            result += bit[index];
        return result;
    }

    int range_sum(int left, int right) {
        return sum(right) - sum(left - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;

    FenwickTree ft(N);
    int anika_lap_count = 0;  // Number of times Anika crosses the finish line
    int anika_position = 0;   // Tracks Anika's position relative to others

    while (Q--) {
        int x;
        cin >> x;

        if (x > 0) {  // Anika overtakes x
            ft.add(x, 1);
            anika_position++;  // She moves forward
        } else {  // Anika gets overtaken by -x
            x = -x;
            ft.add(x, -1);
            anika_position--;  // She moves backward
        }

        // If Anika is at a position lower than 0, she must have crossed the finish line
        if (anika_position < 0) {
            anika_lap_count++;
            anika_position = 0;  // Reset her relative position
        }
    }

    cout << anika_lap_count << '\n';

    return 0;
}

• Subtask 1: 0 / 29
• Subtask 2: 0 / 34
• Subtask 3: 0 / 22
• Subtask 4: 0 / 15