# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
333543 | doowey | NLO (COCI18_nlo) | C++14 | 9 ms | 5120 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
freopen("in.txt", "r", stdin);
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |