| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 333544 |
2020-12-06T23:53:58 Z |
doowey |
NLO (COCI18_nlo) |
C++14 |
|
494 ms |
5232 KB |
#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 ++ ) {
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
