Submission #333543

#TimeUsernameProblemLanguageResultExecution timeMemory
333543dooweyNLO (COCI18_nlo)C++14
0 / 110
9 ms5120 KiB
#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)

nlo.cpp: In function 'int main()':
nlo.cpp:57: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]
   57 |         for(int q = 0; q + 1 < eve.size(); q ++ ) {
      |                        ~~~~~~^~~~~~~~~~~~
nlo.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...