Submission #1157300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157300		_fractal	NLO (COCI18_nlo)	C++20	88 / 110	503 ms	452 KiB

nlo

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

#define F first
#define S second 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 1e5 + 200;
const int M = 1e5;
const int inf = 2e9 + 3;
const ll INF = 1e18;

int n, m, k;
long long X[101], Y[101], R[101];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    cin >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> X[i] >> Y[i] >> R[i];
    }
    long long sum = 0;
    int mx = 0;
    for (int x = 1; x <= n; ++x) {
        vector<pair<pair<int, int>, int>> v = {{{1, m}, 0}};
        for (int i = 1; i <= k; ++i) {
            long long D = R[i] * R[i] - (x - X[i]) * (x - X[i]);
            if (D < 0) {
                continue;
            }
            int l = Y[i] - (floor(sqrt(D)));
            int r = Y[i] + (floor(sqrt(D)));
            vector<pair<pair<int, int>, int>> nv;
            mx = max(mx, sz(v));
            for (auto p : v) {
                if (p.F.F < l && r < p.F.S) {
                    nv.push_back({{p.F.F, l-1}, p.S});
                    nv.push_back({{r+1, p.F.S}, p.S});
                    continue;
                }
                if (p.F.S < l) {
                    nv.push_back(p);
                    continue;
                }
                if (p.F.F < l && l <= p.F.S) {
                    nv.push_back({{p.F.F, l-1}, p.S});
                    continue;
                }
                if (p.F.F <= r && r < p.F.S) {
                    nv.push_back({{r+1, p.F.S}, p.S});
                    continue;
                }
                if (p.F.F > r) {
                    nv.push_back(p);
                    continue;
                }
            }
            nv.push_back({{l, r}, i});
            v = nv;
        }
        for (auto p : v) {
            sum += (k - p.S) * 1ll * (p.F.S - p.F.F + 1);
        }
    }
    assert(mx <= 20);
    cout << sum << '\n';
}

• Subtask 1: 88 / 110