oj.uz

Submission #546928

# Submission time Handle Problem Language Result Execution time Memory
546928 2022-04-09T00:20:41 Z jeroenodb NLO (COCI18_nlo) C++17
110 / 110
 1553 ms 62180 KB 
#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.0 / 110.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 8 ms 900 KB Output is correct
3 Correct 8 ms 3412 KB Output is correct
4 Correct 42 ms 3412 KB Output is correct
5 Correct 47 ms 12664 KB Output is correct
6 Correct 476 ms 26132 KB Output is correct
7 Correct 168 ms 30352 KB Output is correct
8 Correct 983 ms 44100 KB Output is correct
9 Correct 259 ms 51172 KB Output is correct
10 Correct 1553 ms 62180 KB Output is correct