Submission #307298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
307298	2020-09-27T15:05:19 Z	phathnv	NLO (COCI18_nlo)	C++11	110 / 110	641 ms	376 KB

nlo

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "NLO"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int K = 101;

struct segment{
    int l, r, val;
    segment(int _l = 0, int _r = 0, int _val = 0){
        l = _l;
        r = _r;
        val = _val;
    }
};

int m, n, k;
int x[K], y[K], r[K];

int w[K];
bool removed[K];

void readInput(){
    scanf("%d %d %d", &m, &n, &k);
    for(int i = 1; i <= k; i++)
        scanf("%d %d %d", &x[i], &y[i], &r[i]);
}

ll calc(vector <segment> &segs){
    for(int i = 1; i <= k; i++)
        removed[i] = 0;

    vector <ii> event;
    for(segment seg : segs){
        event.push_back(mp(seg.l, seg.val));
        event.push_back(mp(seg.r + 1, -seg.val));
    }
    sort(event.begin(), event.end());

    priority_queue <int> qu;
    int cur = 1;
    ll res = 0;
    qu.push(0);

    for(ii e : event){
        while (removed[qu.top()])
            qu.pop();

        res += (ll) (e.X - cur) * (k - qu.top());
        cur = e.X;
        if (e.Y < 0)
            removed[-e.Y] = 1;
        else
            qu.push(e.Y);
    }
    res += (ll) (n + 1 - cur) * k;
    return res;
}

void solve(){
    ll res = 0;
    for(int row = 1; row <= m; row++){
        vector <segment> segs;
        for(int i = 1; i <= k; i++){
            if (row < x[i] - r[i] || x[i] + r[i] < row)
                continue;
            int h = abs(row - x[i]);
            while ((ll) h * h + (ll) w[i] * w[i] < (ll) r[i] * r[i])
                w[i]++;
            while ((ll) h * h + (ll) w[i] * w[i] > (ll) r[i] * r[i])
                w[i]--;
            segs.push_back(segment(y[i] - w[i], y[i] + w[i], i));
        }
        res += calc(segs);
    }
    cout << res;
}

int main(){
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    readInput();
    solve();
    return 0;
}

Compilation message

nlo.cpp: In function 'void readInput()':
nlo.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     scanf("%d %d %d", &m, &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nlo.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%d %d %d", &x[i], &y[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	256 KB	Output is correct
2	Correct	10 ms	256 KB	Output is correct
3	Correct	9 ms	256 KB	Output is correct
4	Correct	45 ms	256 KB	Output is correct
5	Correct	37 ms	256 KB	Output is correct
6	Correct	258 ms	256 KB	Output is correct
7	Correct	105 ms	376 KB	Output is correct
8	Correct	466 ms	376 KB	Output is correct
9	Correct	197 ms	256 KB	Output is correct
10	Correct	641 ms	376 KB	Output is correct