Submission #307294

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
307294	2020-09-27T14:56:26 Z	phathnv	NLO (COCI18_nlo)	C++11	88 / 110	295 ms	65540 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];
bool removed[K];

vector <segment> segs[N];

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]);
}

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

int main(){
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    readInput();
    prepare();
    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

88.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2944 KB	Output is correct
2	Correct	14 ms	3584 KB	Output is correct
3	Correct	10 ms	3456 KB	Output is correct
4	Correct	48 ms	7680 KB	Output is correct
5	Correct	40 ms	6912 KB	Output is correct
6	Correct	295 ms	36088 KB	Output is correct
7	Correct	119 ms	16632 KB	Output is correct
8	Runtime error	203 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Correct	220 ms	27256 KB	Output is correct
10	Runtime error	222 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)