Submission #68531

#	Time	Username	Problem	Language	Result	Execution time	Memory
68531		imeimi2000	절취선 (JOI14_ho_t5)	C++17	100 / 100	432 ms	66428 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;

struct line {
    int x1, x2, y, i;
    line() {}
    line(int x1, int x2, int y, int i) : x1(x1), x2(x2), y(y), i(i) {}
} lx[100002], ly[100002];
int sx, sy;

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 i < p.i;
    }
    event() {}
    event(int x1, int x2, int y, int t, int i)
        : x1(x1), x2(x2), y(y), t(t), i(i) {}
} ev[200008];
int sze;

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);
}

int compx[200002], compy[200002];
int cpx, cpy;

int compress(int cp[], int sz, int x) {
    return lower_bound(cp, cp + sz, x) - cp + 1;
}

int main() {
    int w, h, n;
    scanf("%d%d%d", &w, &h, &n);
    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[sx++] = line(a, c, b, i + 1);
        else ly[sy++] = line(b, d, a, i + 1);
        compx[cpx++] = a;
        compy[cpy++] = b;
        compx[cpx++] = c;
        compy[cpy++] = d;
    }
    lx[sx++] = line(0, w, 0, n + 1);
    lx[sx++] = line(0, w, h, n + 2);
    ly[sy++] = line(0, h, 0, n + 3);
    ly[sy++] = line(0, h, w, n + 4);
    compx[cpx++] = 0;
    compx[cpx++] = w;
    compy[cpy++] = 0;
    compy[cpy++] = h;
    sort(compx, compx + cpx);
    cpx = unique(compx, compx + cpx) - compx;
    sort(compy, compy + cpy);
    cpy = unique(compy, compy + cpy) - compy;
    
    llong v = n + 4;
    
    for (int it = 0; it < sx; ++it) {
        line &i = lx[it];
        i.x1 = compress(compx, cpx, i.x1);
        i.x2 = compress(compx, cpx, i.x2);
        i.y = compress(compy, cpy, i.y);
        ev[sze++] = event(i.x1, i.x2, i.y, 1, i.i);
    }
    for (int it = 0; it < sy; ++it) {
        line &i = ly[it];
        i.x1 = compress(compy, cpy, i.x1);
        i.x2 = compress(compy, cpy, i.x2);
        i.y = compress(compx, cpx, i.y);
        ev[sze++] = event(i.y, 0, i.x1, 0, i.i);
        ev[sze++] = event(i.y, 0, i.x2, 2, i.i);
    }
    
    sort(ev, ev + sze);
    for (int it = 0; it < sze; ++it) {
        event &i = ev[it];
        if (i.t == 0) {
            update1(1, 1, cpx, i.x1, i.i);
            update(1, 1, cpx, i.x1, 1);
        }
        else if (i.t == 1) {
            update2(1, 1, cpx, i.x1, i.x2, i.i);
            v -= query(1, 1, cpx, i.x1, i.x2);
        }
        else {
            update1(1, 1, cpx, i.x1, 0);
            update(1, 1, cpx, i.x1, -1);
        }
    }
    llong cp = 0;
    for (int i = 1; i <= n + 4; ++i) {
        if (find(i) == i) ++cp;
    }
    printf("%lld\n", cp - v);
	return 0;
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:122: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:125: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