Submission #68374

#TimeUsernameProblemLanguageResultExecution timeMemory
68374imeimi2000절취선 (JOI14_ho_t5)C++17
100 / 100
442 ms12848 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_map> #include <functional> #include <cstring> #include <cmath> #include <ctime> #include <cstdlib> using namespace std; typedef long long llong; typedef long double ld; typedef pair<int, int> pii; typedef pair<llong, llong> pll; int w, h, n, mx; vector<int> compx, compy; struct line { int x1, x2, y, i; bool operator<(const line &p) const { return y < p.y; } int count(const vector<int> &cx, const vector<int> &cy) { x1 = lower_bound(cx.begin(), cx.end(), x1) - cx.begin() + 1; x2 = lower_bound(cx.begin(), cx.end(), x2) - cx.begin() + 1; y = lower_bound(cy.begin(), cy.end(), y) - cy.begin() + 1; return x2 - x1; } }; struct event { int x1, x2, y, t, i; bool operator<(const event &p) const { if (y != p.y) return y < p.y; if (t != p.t) return t < p.t; return x1 < p.x1; } }; struct tree { int sum[1 << 19]; void update(int i, int s, int e, int x, int v) { if (s == e) { sum[i] += v; return; } int m = (s + e) / 2; if (x <= m) update(i << 1, s, m, x, v); else update(i << 1 | 1, m + 1, e, x, v); sum[i] = sum[i << 1] + sum[i << 1 | 1]; } int query(int i, int s, int e, int x, int y) { if (e < x || y < s) return 0; if (x <= s && e <= y) return sum[i]; int m = (s + e) / 2; return query(i << 1, s, m, x, y) + query(i << 1 | 1, m + 1, e, x, y); } int uf[100005]; int seg[1 << 19]; int find(int x) { if (uf[x]) return uf[x] = find(uf[x]); return x; } int merge(int x, int y) { if (x && y) { x = find(x); y = find(y); if (x == y) return 0; uf[x] = y; return 1; } return 0; } void lazy(int i) { if (seg[i]) { merge(seg[i], seg[i << 1]); merge(seg[i], seg[i << 1 | 1]); if (sum[i << 1]) seg[i << 1] = seg[i]; if (sum[i << 1 | 1]) seg[i << 1 | 1] = seg[i]; seg[i] = 0; } } void update1(int i, int s, int e, int x, int v) { if (s == e) { seg[i] = v; return; } lazy(i); int m = (s + e) / 2; if (x <= m) update1(i << 1, s, m, x, v); else update1(i << 1 | 1, m + 1, e, x, v); } void update2(int i, int s, int e, int x, int y, int v) { if (sum[i] == 0) return; if (e < x || y < s) return; if (x <= s && e <= y) { merge(seg[i], v); seg[i] = v; return; } lazy(i); int m = (s + e) / 2; update2(i << 1, s, m, x, y, v); update2(i << 1 | 1, m + 1, e, x, y, v); } } seg; int main() { scanf("%d%d%d", &w, &h, &n); vector<line> lx, ly; for (int i = 0; i < n; ++i) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); if (b == d) lx.push_back({ a, c, b, i + 1 }); else ly.push_back({ b, d, a, i + 1 }); compx.push_back(a); compx.push_back(c); compy.push_back(b); compy.push_back(d); } lx.push_back({ 0, w, 0, n + 1 }); lx.push_back({ 0, w, h, n + 2 }); ly.push_back({ 0, h, 0, n + 3 }); ly.push_back({ 0, h, w, n + 4 }); compx.push_back(0); compx.push_back(w); compy.push_back(0); compy.push_back(h); sort(compx.begin(), compx.end()); compx.erase(unique(compx.begin(), compx.end()), compx.end()); sort(compy.begin(), compy.end()); compy.erase(unique(compy.begin(), compy.end()), compy.end()); mx = compx.size(); llong v = 0; llong e = 0; vector<event> ev; for (line &i : lx) { int r = i.count(compx, compy); v += r + 1; e += r; ev.push_back({ i.x1, i.x2, i.y, 1, i.i }); } for (line &i : ly) { int r = i.count(compy, compx); v += r + 1; e += r; ev.push_back({ i.y, 0, i.x1, 0, i.i }); ev.push_back({ i.y, 0, i.x2, 2, i.i }); } sort(ev.begin(), ev.end()); for (event e : ev) { if (e.t == 0) { seg.update1(1, 1, mx, e.x1, e.i); seg.update(1, 1, mx, e.x1, 1); } else if (e.t == 1) { seg.update2(1, 1, mx, e.x1, e.x2, e.i); v -= seg.query(1, 1, mx, e.x1, e.x2); } else { seg.update1(1, 1, mx, e.x1, 0); seg.update(1, 1, mx, e.x1, -1); } } llong cp = 0; for (int i = 1; i <= n + 4; ++i) { if (seg.find(i) == i) ++cp; } printf("%lld\n", e - v + cp); return 0; }

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:120:10: 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:124:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &a, &b, &c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...