oj.uz

Submission #546926

# Submission time Handle Problem Language Result Execution time Memory
546926 2022-04-09T00:05:21 Z jeroenodb NLO (COCI18_nlo) C++14
77 / 110
 1488 ms 62164 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(m,x+r);++i) {
            int dif = (x-i);
            int delta = int(sqrt(ll(r)*r-ll(dif)*dif));
            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

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.0 / 110.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 824 KB Output is correct
2 Correct 7 ms 816 KB Output is correct
3 Incorrect 3 ms 1844 KB Output isn't correct
4 Correct 38 ms 3324 KB Output is correct
5 Correct 41 ms 12684 KB Output is correct
6 Incorrect 330 ms 19860 KB Output isn't correct
7 Correct 142 ms 30372 KB Output is correct
8 Correct 992 ms 44108 KB Output is correct
9 Incorrect 235 ms 46796 KB Output isn't correct
10 Correct 1488 ms 62164 KB Output is correct