oj.uz

Submission #1003561

# Submission time Handle Problem Language Result Execution time Memory
1003561 2024-06-20T13:02:40 Z ThegeekKnight16 Autobahn (COI21_autobahn) C++17
0 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K, X;
    cin >> N >> K >> X;
    vector<tuple<int, int, int>> sweep;
    for (int i = 0; i < N; i++)
    {
        int L, T, R;
        cin >> L >> T >> R;
        T = min(L+T-1, R+1);
        sweep.emplace_back(L, 0, -1);
        sweep.emplace_back(T+1, 1, -1);
        sweep.emplace_back(R+1, 2, -1);
        sweep.emplace_back(T, 3, 3*i); sweep.emplace_back(T+X, 4, 3*i);
        sweep.emplace_back(R-X, 3, 3*i + 1); sweep.emplace_back(R, 4, 3*i + 1);
        sweep.emplace_back(L-1, 3, 3*i + 2); sweep.emplace_back(L+X-1, 4, 3*i + 2);
    }
    vector<int> possResp(3*N);
    sort(sweep.begin(), sweep.end());
    int totPeople = 0, totPaying = 0, totPay = 0, lastX = 0, resp = 0;
    for (auto [x, type, id] : sweep)
    {
        totPay += (int)(totPeople >= K) * totPaying * (x - lastX);
        lastX = x;
        // cerr << "x: " << x << ", totPeople: " << totPeople << ", totPaying: " << totPaying << ", totPay: " << totPay << '\n';
        if (type == 0) totPeople++;
        else if (type == 1) totPaying++;
        else if (type == 2) totPeople--, totPaying--;
        else if (type == 3) possResp[id] = totPay;
        else resp = max(resp, totPay - possResp[id]);
    }
    cout << resp << '\n';
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -