Submission #332293

#TimeUsernameProblemLanguageResultExecution timeMemory
332293arnold518절취선 (JOI14_ho_t5)C++14
0 / 100
185 ms11348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; struct Line { int x1, y1, x2, y2; }; int W, H, N, M, SX, SY; Line A[MAXN+10], B[MAXN+10]; vector<int> xcomp, ycomp; ll V, E, C=1; struct BIT { int tree[MAXN+10]; void update(int i, int x) { for(; i<=SY; i+=(i&-i)) tree[i]+=x; } int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; } int query(int l, int r) { return query(r)-query(l-1); } }bit; int main() { int t; scanf("%d%d%d", &W, &H, &t); for(int i=1; i<=t; i++) { Line p; scanf("%d%d%d%d", &p.x1, &p.y1, &p.x2, &p.y2); xcomp.push_back(p.x1); xcomp.push_back(p.x2); ycomp.push_back(p.y1); ycomp.push_back(p.y2); if(p.x1==p.x2) B[++M]=p; else A[++N]=p; } xcomp.push_back(0); ycomp.push_back(0); xcomp.push_back(W); ycomp.push_back(H); A[++N]={0, 0, W, 0}; A[++N]={0, H, W, H}; B[++M]={0, 0, 0, H}; B[++M]={W, 0, W, H}; sort(xcomp.begin(), xcomp.end()); xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end()); sort(ycomp.begin(), ycomp.end()); ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end()); SX=xcomp.size(); SY=ycomp.size(); for(int i=1; i<=N; i++) { A[i].x1=lower_bound(xcomp.begin(), xcomp.end(), A[i].x1)-xcomp.begin()+1; A[i].x2=lower_bound(xcomp.begin(), xcomp.end(), A[i].x2)-xcomp.begin()+1; A[i].y1=lower_bound(ycomp.begin(), ycomp.end(), A[i].y1)-ycomp.begin()+1; A[i].y2=lower_bound(ycomp.begin(), ycomp.end(), A[i].y2)-ycomp.begin()+1; } for(int i=1; i<=M; i++) { B[i].x1=lower_bound(xcomp.begin(), xcomp.end(), B[i].x1)-xcomp.begin()+1; B[i].x2=lower_bound(xcomp.begin(), xcomp.end(), B[i].x2)-xcomp.begin()+1; B[i].y1=lower_bound(ycomp.begin(), ycomp.end(), B[i].y1)-ycomp.begin()+1; B[i].y2=lower_bound(ycomp.begin(), ycomp.end(), B[i].y2)-ycomp.begin()+1; } for(int i=1; i<=N; i++) { E+=A[i].x2-A[i].x1; V+=A[i].x2-A[i].x1+1; } for(int i=1; i<=M; i++) { E+=B[i].y2-B[i].y1; V+=B[i].y2-B[i].y1+1; } sort(B+1, B+M+1, [&](const Line &p, const Line &q) { return p.x1<q.x1; }); vector<pair<pll, int>> VV; for(int i=1; i<=N; i++) { VV.push_back({{A[i].x1, A[i].y1}, 1}); VV.push_back({{A[i].x2+1, A[i].y1}, -1}); } sort(VV.begin(), VV.end()); for(int i=1, j=0; i<=M; i++) { for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++) { bit.update(VV[j].first.second, VV[j].second); } V-=bit.query(B[i].y1, B[i].y2); } ll ans=C-V+E; printf("%lld\n", ans); }

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:104:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
      |         ~^~~~~~~~~~
2014_ho_t5.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d%d%d", &W, &H, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |   scanf("%d%d%d%d", &p.x1, &p.y1, &p.x2, &p.y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...