Submission #154732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154732	2019-09-24T09:53:40 Z	hocky	NLO (COCI18_nlo)	C++14	110 / 110	815 ms	504 KB

nlo

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#define pb push_back
using namespace std;
typedef long long LL;

inline void fasterios(){
    //Do not use if interactive
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

LL n,m,k;
struct dt{
    LL x,y,r;
};
vector <dt> all;
struct dtl{
    bool isOn;
    LL pos, idx;
    bool operator<(const dtl &other)const{
        if(pos != other.pos) return pos < other.pos;
        return isOn > other.isOn;
    }
};

int main(){
    cin >> n >> m;
    cin >> k;
    for(int i = 1;i <= k;i++){
        dt tmp; cin >> tmp.x >> tmp.y >> tmp.r;
        all.pb(tmp);
    }
    reverse(all.begin(),all.end());
    LL ans = 0;
    for(int i = 1;i <= n;i++){
        vector <dtl> lines;
        lines.pb({1,1,k});
        lines.pb({0,m,k});
        for(int j = 0;j < all.size();j++){
            LL dist_x = (all[j].x-i);
            LL diff = (all[j].r*all[j].r) - (dist_x*dist_x);
            if(diff < 0) continue;
            diff = sqrt(diff);
            lines.pb({1,all[j].y-diff,j});
            lines.pb({0,all[j].y+diff,j});
        }
        sort(lines.begin(),lines.end());
        set <LL> active_lines;
        LL pre = 0;
        for(int j = 0;j < lines.size();j++){
            if(lines[j].isOn == 1){
                if(pre < lines[j].pos-1){
                    LL smallest = *(active_lines.begin());
                    ans += (lines[j].pos-1-pre)*smallest;
                    pre = lines[j].pos-1;
                }
                active_lines.insert(lines[j].idx);
            }else{
                if(pre < lines[j].pos){
                    LL smallest = *(active_lines.begin());
                    ans += (lines[j].pos-pre)*smallest;
                    pre = lines[j].pos;
                }
                active_lines.erase(lines[j].idx);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

nlo.cpp: In function 'int main()':
nlo.cpp:43:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < all.size();j++){
                       ~~^~~~~~~~~~~~
nlo.cpp:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < lines.size();j++){
                       ~~^~~~~~~~~~~~~~

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	15 ms	376 KB	Output is correct
3	Correct	11 ms	256 KB	Output is correct
4	Correct	57 ms	504 KB	Output is correct
5	Correct	46 ms	368 KB	Output is correct
6	Correct	336 ms	376 KB	Output is correct
7	Correct	138 ms	256 KB	Output is correct
8	Correct	611 ms	376 KB	Output is correct
9	Correct	255 ms	376 KB	Output is correct
10	Correct	815 ms	376 KB	Output is correct