Submission #546928

#	Time	Username	Problem	Language	Result	Execution time	Memory
546928		jeroenodb	NLO (COCI18_nlo)	C++17	110 / 110	1553 ms	62180 KiB

nlo

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int main() {
    int n,m,k; cin >> n >> m >> k;
    vector<map<int,int>> mp(n+1);
    for(int i=1;i<=n;++i) {
        mp[i] = {{1,k},{m+1,0}};
    }
    while(k--) {
        int x,y,r; cin >> x >> y >> r;
        for(int i=max(x-r,1);i<=min(n,x+r);++i) {
            int dif = (x-i);
            int delta = ll(sqrtl(ll(r)*r-ll(dif)*dif+0.5L));
            int lo = max(1,y-delta), hi = min(m,y+delta)+1;
            // range set on [lo,hi) to k
            auto& s = mp[i];
            auto it = s.upper_bound(lo);
            int last= prev(it)->second;
            while(it!=s.end() and it->first <= hi) {
                last = it->second;
                it = s.erase(it);
            }
            s[hi]=last;
            s[lo]=k;
        }
    }
    ll ans=0;
    for(auto& s : mp) {
        int lastx=1,last=0;
        for(auto [x,h] : s) {
            ans+=ll(x-lastx)*last;
            lastx=x,last=h;
        }
    }
    cout << ans << '\n';
}

• Subtask 1: 110 / 110