제출 #1157278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157278		_fractal	NLO (COCI18_nlo)	C++20	55 / 110	3095 ms	4420 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];

template<typename T>
struct segtree_push {
    T t[N << 2], p[N << 2], neu;

    inline T merge(T a, T b) {
        return a + b;
    }

    void build(int v = 1, int tl = 1, int tr = m) {
        p[v] = 0;
        t[v] = 0;
        if (tl == tr) {
            return;
        }
        int tm = tl + tr >> 1;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
    }

    void push(int v, int tl, int tr) {
        if (p[v] == 0) return;
        if (tl != tr) {
            p[v * 2] = p[v];
            p[v * 2 + 1] = p[v];
        }
        t[v] = (tr - tl + 1) * p[v];
        p[v] = 0;
    }

    void upd(int l, int r, T val, int v = 1, int tl = 1, int tr = m) {
        push(v, tl, tr);
        if (l <= tl && tr <= r) {
            p[v] = val;
            push(v, tl, tr);
            return;
        }
        if (r < tl || tr < l) {
            return;
        }
        int tm = tl + tr >> 1;
        upd(l, r, val, v * 2, tl, tm);
        upd(l, r, val, v * 2 + 1, tm + 1, tr);
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }

    T get(int l, int r, int v = 1, int tl = 1, int tr = m) {
        push(v, tl, tr);
        if (l <= tl && tr <= r) {
            return t[v];
        }
        if (r < tl || tr < l) {
            return neu;
        }
        int tm = tl + tr >> 1;
        return merge(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
    }
};

segtree_push<long long> t;

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;
    for (int x = 1; x <= n; ++x) {
        t.build();
        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)));
            t.upd(l, r, i);
        }
        sum += k * m - t.t[1];
    }
    cout << sum << '\n';
}

• Subtask 1: 55 / 110