Submission #546927

#	Time	Username	Problem	Language	Result	Execution time	Memory
546927		jeroenodb	NLO (COCI18_nlo)	C++14	77 / 110	1625 ms	62084 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(m,x+r);++i) {
            int dif = (x-i);
            int delta = int(sqrtl(ll(r)*r-ll(dif)*dif+0.2L));
            int lo = max(1,y-delta), hi = min(m,y+delta)+1;
            // range set
            auto& s = mp[i];
            auto it = s.upper_bound(lo);
            int last= prev(it)->second;
            while(it->first < hi) {
                last = it->second;
                it = s.erase(it);
            }
            if(it->first!=hi) s[hi]=last;
            s[lo]=k;
        }
    }
    ll ans=0;
    for(auto& s : mp) {
        int lastx=0,last=0;
        for(auto [x,h] : s) {
            ans+=ll(x-lastx)*last;
            lastx=x,last=h;
        }
    }
    cout << ans;
}

Compilation message (stderr)

nlo.cpp: In function 'int main()':
nlo.cpp:39:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |         for(auto [x,h] : s) {
      |                  ^

• Subtask 1: 77 / 110