제출 #333380

#제출 시각아이디문제언어결과실행 시간메모리
333380arnold518절취선 (JOI14_ho_t5)C++14
10 / 100
1307 ms262148 KiB
#pragma GCC optimize ("O3") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; const int MAXV = 3.7e6; struct Line { int x1, y1, x2, y2, p; }; 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 LC[MAXV+10], RC[MAXV+10]; int ncnt; int newNode() { if(ncnt+1==MAXV) while(1); return ++ncnt; } vector<int> adj[MAXV+10]; vector<int> radj[MAXN+10]; void addEdge(int u, int v) { //printf("%d %d\n", u, v); if(u==-1 || v==-1) return; adj[u].push_back(v); } int update(int node, int tl, int tr, int p, int k) { if(p<tl || tr<p) return node; if(tl==tr) { if(k>0) return k; return -1; } int ret=newNode(); int mid=tl+tr>>1; LC[ret]=update(LC[node], tl, mid, p, k); RC[ret]=update(RC[node], mid+1, tr, p, k); addEdge(LC[ret], ret); addEdge(RC[ret], ret); return ret; } void query(int node, int tl, int tr, int l, int r, int k) { if(r<tl || tr<l) return; if(l<=tl && tr<=r) { addEdge(node, k); radj[k].push_back(node); return; } int mid=tl+tr>>1; query(LC[node], tl, mid, l, r, k); query(RC[node], mid+1, tr, l, r, k); } bool vis[MAXV+10]; vector<int> S; void dfs(int now) { vis[now]=true; for(int nxt : adj[now]) { if(vis[nxt]) continue; dfs(nxt); } S.push_back(now); } int scc[MAXV+10], scnt; void dfs2(int now) { scc[now]=scnt; if(now>N+M) { int nxt=LC[now]; if(nxt!=-1 && !scc[nxt]) dfs2(nxt); nxt=RC[now]; if(nxt!=-1 && !scc[nxt]) dfs2(nxt); } else for(int nxt : radj[now]) { if(scc[nxt]) continue; dfs2(nxt); } } 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; A[i].p=newNode(); } 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; B[i].p=newNode(); } xcomp.clear(); xcomp.shrink_to_fit(); ycomp.clear(); ycomp.shrink_to_fit(); 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); } int root; VV.clear(); VV.shrink_to_fit(); for(int i=1; i<=N; i++) { VV.push_back({{A[i].x1, A[i].y1}, A[i].p}); VV.push_back({{A[i].x2+1, A[i].y1}, 0}); } sort(VV.begin(), VV.end()); root=newNode(); //makeTree(root, 1, SY); for(int i=1, j=0; i<=M; i++) { for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++) { root=update(root, 1, SY, VV[j].first.second, VV[j].second); //printf("!!%d\n", VV[j].second); } query(root, 1, SY, B[i].y1, B[i].y2, B[i].p); //printf("??%d\n", B[i].p); } VV.clear(); VV.shrink_to_fit(); for(int i=1; i<=M; i++) { VV.push_back({{B[i].y1, B[i].x1}, B[i].p}); VV.push_back({{B[i].y2+1, B[i].x1}, 0}); } sort(VV.begin(), VV.end()); sort(A+1, A+N+1, [&](const Line &p, const Line &q) { return p.y1<q.y1; }); root=newNode(); //makeTree(root, 1, SX); for(int i=1, j=0; i<=N; i++) { for(; j<VV.size() && VV[j].first.first<=A[i].y1; j++) { root=update(root, 1, SX, VV[j].first.second, VV[j].second); } query(root, 1, SX, A[i].x1, A[i].x2, A[i].p); } VV.clear(); VV.shrink_to_fit(); for(int i=1; i<=N+M; i++) { if(vis[i]) continue; dfs(i); } reverse(S.begin(), S.end()); for(auto it : S) { if(scc[it]) continue; ++scnt; dfs2(it); } sort(scc+1, scc+N+M+1); C=unique(scc+1, scc+N+M+1)-scc-1; ll ans=C-V+E; printf("%lld\n", ans); }

컴파일 시 표준 에러 (stderr) 메시지

2014_ho_t5.cpp: In function 'int update(int, int, int, int, int)':
2014_ho_t5.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid=tl+tr>>1;
      |          ~~^~~
2014_ho_t5.cpp: In function 'void query(int, int, int, int, int, int)':
2014_ho_t5.cpp:81:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |  int mid=tl+tr>>1;
      |          ~~^~~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:195: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]
  195 |   for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
      |         ~^~~~~~~~~~
2014_ho_t5.cpp:216: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]
  216 |   for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
      |         ~^~~~~~~~~~
2014_ho_t5.cpp:242: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]
  242 |   for(; j<VV.size() && VV[j].first.first<=A[i].y1; j++)
      |         ~^~~~~~~~~~
2014_ho_t5.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |  scanf("%d%d%d", &W, &H, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |   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...