Garage

This is a direct simulation. Maintain a set<int> of available spots (auto-sorted, smallest first). Maintain a queue<int> of waiting cars. Process each event: Arrival of car c: If a spot is free, assign the smallest; o...

Updated May 21, 2026

Track IOI

Year 2009

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

A parking garage has $N$ spots with rates $r_1, \ldots, r_N$ (rate per unit weight). There are $M$ cars with weights $w_1, \ldots, w_M$. Cars arrive and depart in a given sequence of $2M$ events. On arrival, a car is assigned the lowest-numbered free spot; if none is free, it waits in a FIFO queue. On departure, the freed spot is offered to the first queued car (which gets the lowest-numbered free spot). The parking fee for a car assigned spot $j$ is $r_j \cdot w_{\text{car}}$. Compute the total revenue.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution

This is a direct simulation.

Maintain a set<int> of available spots (auto-sorted, smallest first).
Maintain a queue<int> of waiting cars.

Process each event:

\textbf{Arrival of car $c$}: If a spot is free, assign the smallest; otherwise enqueue.
\textbf{Departure of car $c$}: Free its spot. If the queue is non-empty, assign the smallest free spot to the front car.
enumerate

Complexity

Time: $O(M \log N)$.
Space: $O(N + M)$.

C++ Solution

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

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

    int N, M;
    cin >> N >> M;

    vector<int> rate(N + 1);
    for(int i = 1; i <= N; i++) cin >> rate[i];

    vector<int> weight(M + 1);
    for(int i = 1; i <= M; i++) cin >> weight[i];

    set<int> available;
    for(int i = 1; i <= N; i++) available.insert(i);

    queue<int> waiting;
    map<int, int> carSpot;
    long long revenue = 0;

    for(int e = 0; e < 2 * M; e++){
        int x;
        cin >> x;
        if(x > 0){
            if(!available.empty()){
                int spot = *available.begin();
                available.erase(available.begin());
                carSpot[x] = spot;
                revenue += (long long)rate[spot] * weight[x];
            } else {
                waiting.push(x);
            }
        } else {
            int car = -x;
            int spot = carSpot[car];
            carSpot.erase(car);
            available.insert(spot);
            if(!waiting.empty()){
                int nextCar = waiting.front();
                waiting.pop();
                int bestSpot = *available.begin();
                available.erase(available.begin());
                carSpot[nextCar] = bestSpot;
                revenue += (long long)rate[bestSpot] * weight[nextCar];
            }
        }
    }

    cout << revenue << "\n";
    return 0;
}

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 2009 - Garage
// Straightforward simulation with a set of available spots and a FIFO queue.
// O(M log N) time.
#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    cin >> N >> M;

    vector<int> rate(N + 1);
    for (int i = 1; i <= N; i++) cin >> rate[i];

    vector<int> weight(M + 1);
    for (int i = 1; i <= M; i++) cin >> weight[i];

    // Available spots ordered by number (smallest first).
    set<int> available;
    for (int i = 1; i <= N; i++) available.insert(i);

    queue<int> waiting;          // FIFO queue of cars waiting for a spot
    map<int, int> carSpot;       // car -> assigned spot
    long long revenue = 0;

    int events = 2 * M;
    for (int e = 0; e < events; e++) {
        int x;
        cin >> x;

        if (x > 0) {
            // Car x arrives.
            if (!available.empty()) {
                int spot = *available.begin();
                available.erase(available.begin());
                carSpot[x] = spot;
                revenue += (long long)rate[spot] * weight[x];
            } else {
                waiting.push(x);
            }
        } else {
            // Car -x departs.
            int car = -x;
            int spot = carSpot[car];
            carSpot.erase(car);
            available.insert(spot);

            // Assign the smallest available spot to the next waiting car.
            if (!waiting.empty()) {
                int nextCar = waiting.front();
                waiting.pop();
                int bestSpot = *available.begin();
                available.erase(available.begin());
                carSpot[nextCar] = bestSpot;
                revenue += (long long)rate[bestSpot] * weight[nextCar];
            }
        }
    }

    cout << revenue << "\n";
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/2009/garage/solution.texC++ implementationcompetitive_programming/ioi/2009/garage/solution.cpp