Submission #307294

#	Time	Username	Problem	Language	Result	Execution time	Memory
307294		phathnv	NLO (COCI18_nlo)	C++11	88 / 110	295 ms	65540 KiB

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 (stderr)

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 / 110