답안 #333544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333544	2020-12-06T23:53:58 Z	doowey	NLO (COCI18_nlo)	C++14	110 / 110	494 ms	5232 KB

nlo

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
const int K = 105;
int x[K], y[K], r[K];
int xl[K], xr[K];
vector<int> add[N];
vector<int> rem[N];

ll sq(ll x){
    return x * 1ll * x;
}

bool active[K];
bool have[K];

int main(){
    fastIO;
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= k ; i ++ ){
        cin >> x[i] >> y[i] >> r[i];
        add[x[i]-r[i]].push_back(i);
        xl[i]=xr[i]=y[i];
        rem[x[i]+r[i]+1].push_back(i);
    }
    ll soln = 0;
    int delta;
    for(int row = 1; row <= n; row ++ ){
        for(auto xx : add[row]) active[xx]=true;
        for(auto xx : rem[row]) active[xx]=false;
        vector<pii> eve;
        eve.push_back(mp(1,0));
        eve.push_back(mp(m+1,0));
        for(int i = k; i >= 0 ; i -- ){
            have[i]=false;
            if(!active[i]) continue;
            delta = sqrt(sq(r[i])-sq(row-x[i]));
            xl[i]=y[i]-delta;
            xr[i]=y[i]+delta;
            eve.push_back(mp(xl[i], i));
            eve.push_back(mp(xr[i] + 1, i));
        }
        sort(eve.begin(), eve.end());
        priority_queue<int> maxi;
        for(int q = 0; q + 1 < eve.size(); q ++ ) {
            if(have[eve[q].se]){
                have[eve[q].se]=false;
            }
            else{
                have[eve[q].se]=true;
                maxi.push(eve[q].se);
            }
            while(!have[maxi.top()]) maxi.pop();
            soln += (eve[q+1].fi - eve[q].fi) * 1ll * (k-maxi.top());
        }

    }
    cout << soln << "\n";
    return 0;
}

Compilation message

nlo.cpp: In function 'int main()':
nlo.cpp:56:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int q = 0; q + 1 < eve.size(); q ++ ) {
      |                        ~~~~~~^~~~~~~~~~~~

Subtask #1

110.0 / 110.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	5100 KB	Output is correct
2	Correct	14 ms	5100 KB	Output is correct
3	Correct	10 ms	5100 KB	Output is correct
4	Correct	41 ms	5100 KB	Output is correct
5	Correct	31 ms	5100 KB	Output is correct
6	Correct	205 ms	5100 KB	Output is correct
7	Correct	82 ms	5100 KB	Output is correct
8	Correct	374 ms	5232 KB	Output is correct
9	Correct	152 ms	5228 KB	Output is correct
10	Correct	494 ms	5228 KB	Output is correct