Submission #522845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
522845	2022-02-06T03:49:18 Z	KoD	NLO (COCI18_nlo)	C++17	110 / 110	96 ms	16324 KB

nlo

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

constexpr ll sq(const ll x) {
    return x * x;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M, K;
    std::cin >> N >> M >> K;
    vector<int> X(K), Y(K), R(K);
    for (int i = 0; i < K; ++i) {
        std::cin >> X[i] >> Y[i] >> R[i];
        X[i] -= 1, Y[i] -= 1;
    }
    vector<std::map<int, int>> remain(N);
    for (int i = 0; i < N; ++i) {
        remain[i].emplace(M, 0);
    }
    ll subt = 0;
    for (int i = K - 1; i >= 0; --i) {
        const auto process = [&](const int x, const int l, const int r) {
            auto& map = remain[x];
            {
                auto itr = map.upper_bound(l);
                if (itr == map.end()) return;
                const auto [b, a] = *itr;
                if (r <= a) return;
                subt += (ll)(i + 1) * (std::min(r, b) - std::max(l, a));
                map.erase(itr);
                if (a < l) {
                    map[l] = a;
                }
                if (r < b) {
                    map[b] = r;
                }
            }
            auto itr = map.upper_bound(l);
            while (itr != map.end()) {
                const auto [b, a] = *itr;
                if (r <= a) {
                    break;
                }
                subt += (ll)(i + 1) * (std::min(r, b) - std::max(l, a));
                if (r < b) {
                    map.erase(itr);
                    map[b] = r;
                    break;
                } else {
                    itr = map.erase(itr);
                }
            }
        };
        int left = Y[i], right = Y[i];
        for (int x = X[i] - R[i]; x <= X[i]; ++x) {
            while (sq(X[i] - x) + sq(Y[i] - (left - 1)) <= sq(R[i])) {
                left -= 1;
            }
            while (sq(X[i] - x) + sq(Y[i] - right) <= sq(R[i])) {
                right += 1;
            }
            process(x, left, right);
        }
        for (int x = X[i] + 1; x <= X[i] + R[i]; ++x) {
            while (sq(X[i] - x) + sq(Y[i] - left) > sq(R[i])) {
                left += 1;
            }
            while (sq(X[i] - x) + sq(Y[i] - (right - 1)) > sq(R[i])) {
                right -= 1;
            }
            process(x, left, right);
        }
    }
    std::cout << (ll)N * M * K - subt << '\n';
    return 0;
}

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	4 ms	1612 KB	Output is correct
4	Correct	6 ms	1100 KB	Output is correct
5	Correct	17 ms	3512 KB	Output is correct
6	Correct	41 ms	7824 KB	Output is correct
7	Correct	35 ms	9216 KB	Output is correct
8	Correct	80 ms	11480 KB	Output is correct
9	Correct	75 ms	16324 KB	Output is correct
10	Correct	96 ms	14916 KB	Output is correct