제출 #51760

#제출 시각아이디문제언어결과실행 시간메모리
51760model_code절취선 (JOI14_ho_t5)C++17
100 / 100
402 ms13664 KiB
#include<cstdio> #include<algorithm> #include<set> #include<vector> using namespace std; const int MAXN = 100020; struct seg_tree { static const int DEPTH = 19; static const int SIZE = 1<<DEPTH; int bit[1<<(DEPTH+1)]; int renew[1<<(DEPTH+1)]; seg_tree() { } void init() { for(int i=0;i<2*SIZE;i++) bit[i] = renew[i] = 0; } void add(int p, int v) { p += SIZE; while(p){ bit[p] += v; p >>= 1; } } int query(int l, int r) { l += SIZE; r += SIZE; int ret = 0; while(l < r){ if(l&1) ret += bit[l++]; if(r&1) ret += bit[--r]; l >>= 1; r >>= 1; } return ret; } void set_renew(int l, int r) { l += SIZE; r += SIZE; while(l < r){ if(l&1) renew[l++] = 1; if(r&1) renew[--r] = 1; l >>= 1; r >>= 1; } } bool is_renew(int p) { p += SIZE; while(p){ if(renew[p]) return true; p >>= 1; } return false; } void unset_renew(int p) { p += SIZE; for(int i=DEPTH-1;i>0;i--){ if(renew[p >> i]){ renew[p >> i] = 0; renew[(p>>i)*2] = renew[(p>>i)*2+1] = 1; } } renew[p] = 0; } }; struct action { int pos, act, left, right; action(int p, int a, int l, int r) { pos = p; act = a; left = l; right = r; } }; inline bool operator<(const action& a, const action& b) { return a.pos < b.pos || (a.pos == b.pos && a.act < b.act); } int W, H, N; int x1[MAXN], y1[MAXN], x2[MAXN], y2[MAXN]; vector<int> uf; seg_tree seg; int target[MAXN*2]; int root(int p) { return (uf[p] < 0) ? p : (uf[p] = root(uf[p])); } bool join(int p, int q) { p = root(p); q = root(q); if(p==q) return false; if(uf[p] < uf[q]) swap(p, q); uf[p] = uf[q]; uf[q] = p; return true; } void adjust(int p) { if(seg.is_renew(p)){ uf.push_back(-1); seg.unset_renew(p); target[p] = uf.size() - 1; } } int main() { scanf("%d%d%d", &W, &H, &N); for(int i=0;i<N;i++){ scanf("%d%d%d%d", x1+i, y1+i, x2+i, y2+i); if(x1[i] > x2[i]) swap(x1[i], x2[i]); if(y1[i] > y2[i]) swap(y1[i], y2[i]); } for(int i=0;i<2*N;i++) target[i] = -1; x1[N ] = 0; y1[N ] = 0; x2[N ] = W; y2[N ] = 0; x1[N+1] = 0; y1[N+1] = 0; x2[N+1] = 0; y2[N+1] = H; x1[N+2] = W; y1[N+2] = 0; x2[N+2] = W; y2[N+2] = H; x1[N+3] = 0; y1[N+3] = H; x2[N+3] = W; y2[N+3] = H; N += 4; vector<int> xs; for(int i=0;i<N;i++){ xs.push_back(x1[i]); xs.push_back(x2[i]); } xs.push_back(-1); sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for(int i=0;i<N;i++){ x1[i] = lower_bound(xs.begin(), xs.end(), x1[i]) - xs.begin(); x2[i] = lower_bound(xs.begin(), xs.end(), x2[i]) - xs.begin(); } set<int> S; S.insert(0); target[0] = 0; uf.push_back(-1); vector<action> A; for(int i=0;i<N;i++){ if(x1[i] == x2[i]){ A.push_back(action(y1[i], 0, x1[i], -1)); A.push_back(action(y2[i], 2, x1[i], -1)); }else{ A.push_back(action(y1[i], 1, x1[i], x2[i])); } } sort(A.begin(), A.end()); long long ret = 0; for(int i=0;i<A.size();i++){ action V = A[i]; if(V.act == 0){ int lf = *--S.lower_bound(V.left); adjust(lf); adjust(V.left); target[V.left] = target[lf]; S.insert(V.left); seg.add(V.left, 1); }else if(V.act == 1){ int count = seg.query(V.left, V.right+1); if(count < 2) continue; ret += count - 1; seg.set_renew(V.left, *--S.upper_bound(V.right)); }else if(V.act == 2){ int lf = *--S.lower_bound(V.left); adjust(lf); adjust(V.left); if(join(target[lf], target[V.left])) --ret; S.erase(V.left); seg.add(V.left, -1); } } printf("%lld\n", ret); return 0; }

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

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:183:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
2014_ho_t5.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &W, &H, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", x1+i, y1+i, x2+i, y2+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...