답안 #230508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230508 2020-05-10T09:17:51 Z Vimmer NLO (COCI18_nlo) C++14
88 / 110
595 ms 65540 KB
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)

using namespace std;

//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;

typedef short int si;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


vector <pair <int, pair <int, int> > > g[N];

bool gd(ll sx, ll sy, ll x, ll y, ll r)
{
    ll rst = (sx - x) * (sx - x) + (sy - y) * (sy - y);

    return r * r >= rst;
}
int main()
{
   // freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, m, k;

    cin >> n >> m >> k;

    for (int i = 0; i < k; i++)
    {
        int sx, sy, R;

        cin >> sx >> sy >> R;

        for (int x = 1; x <= n; x++)
        {
            if (!gd(sx, sy, x, sy, R)) continue;

            int l = 1, r = sy;

            while (l < r)
            {
                int md = (l + r) >> 1;

                if (gd(sx, sy, x, md, R)) r = md; else l = md + 1;
            }

            int L = l;

            l = sy, r = m;

            while (l + 1 < r)
            {
                int md = (l + r) >> 1;

                if (gd(sx, sy, x, md, R)) l = md; else r = md - 1;
            }

            while (!gd(sx, sy, x, l, R)) l--;

            while (gd(sx, sy, x, l + 1, R)) l++;

            int R = l;

            g[x].pb({i + 1, {L, R}});
        }
    }

    ll ans = n * m * k;

    for (int x = 1; x <= n; x++)
    {
        while (sz(g[x]) > 0)
        {
            ll L = g[x].back().S.F, R = g[x].back().S.S;

            ll nm = g[x].back().F; g[x].pop_back();

            ans -= nm * (R - L + 1);

            vector <pair <int, pair <int, int> > > vr; vr.clear();

            for (auto it : g[x])
            {
                int l = it.S.F, r = it.S.S;

                if (L <= l && r <= R) continue;

                if (l <= L && R <= r) {vr.pb({it.F, {l, L - 1}}); vr.pb({it.F, {R + 1, r}});}

                if (r < L || R < l) {vr.pb(it); continue;}

                if (r < R) r = L - 1;
                  else l = R + 1;

                vr.pb({it.F, {l, r}});
            }

            g[x] = vr;
        }
    }
    cout << ans << endl;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2944 KB Output is correct
2 Correct 26 ms 4480 KB Output is correct
3 Correct 17 ms 3584 KB Output is correct
4 Correct 86 ms 9464 KB Output is correct
5 Correct 146 ms 8056 KB Output is correct
6 Correct 551 ms 46328 KB Output is correct
7 Correct 219 ms 17016 KB Output is correct
8 Runtime error 476 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 595 ms 38708 KB Output is correct
10 Runtime error 526 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)