Submission #230508

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
230508	2020-05-10T09:17:51 Z	Vimmer	NLO (COCI18_nlo)	C++14	88 / 110	595 ms	65540 KB

nlo

#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;
}

Subtask #1

88.0 / 110.0

#	Verdict	Execution time	Memory	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)