Submission #68374

#	Time	Username	Problem	Language	Result	Execution time	Memory
68374		imeimi2000	절취선 (JOI14_ho_t5)	C++17	100 / 100	442 ms	12848 KiB

2014_ho_t5

#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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50