oj.uz

Submission #230512

# Submission time Handle Problem Language Result Execution time Memory
230512 2020-05-10T09:24:17 Z Vimmer NLO (COCI18_nlo) C++14
110 / 110
 2537 ms 504 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;


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;

    ll ans = n * m * k;

    int sx[k], sy[k], R[k];

    for (int i = 0; i < k; i++) cin >> sx[i] >> sy[i] >> R[i];

    for (int x = 1; x <= n; x++)
    {
        vector <pair < int, pair <int, int> > > g; g.clear();

        for (int j = 0; j < k; j++)
        {
            if (!gd(sx[j], sy[j], x, sy[j], R[j])) continue;

            int l = 1, r = sy[j];

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

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

            int L = l;

            l = sy[j], r = m;

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

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

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

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

            int R = l;

            g.pb({j + 1, {L, R}});
        }

        while (sz(g) > 0)
        {
            ll L = g.back().S.F, R = g.back().S.S;

            ll nm = g.back().F; g.pop_back();

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

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

            for (auto it : g)
            {
                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 = vr;
        }
    }
    cout << ans << endl;
}

Subtask #1
110.0 / 110.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 28 ms 384 KB Output is correct
3 Correct 18 ms 384 KB Output is correct
4 Correct 104 ms 384 KB Output is correct
5 Correct 186 ms 384 KB Output is correct
6 Correct 679 ms 504 KB Output is correct
7 Correct 273 ms 256 KB Output is correct
8 Correct 1313 ms 504 KB Output is correct
9 Correct 726 ms 384 KB Output is correct
10 Correct 2537 ms 396 KB Output is correct