oj.uz

답안 #55170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55170 2018-07-06T08:09:13 Z 강태규(#1525) 절취선 (JOI14_ho_t5) C++11
0 / 100
 366 ms 14560 KB 
#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;
vector<int> compx, compy;
struct line {
    int x1, x2, y;
    bool operator<(const line &p) const {
        return y < p.y;
    }
    void compress(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;
    }
};

struct event {
    int x, y, c;
    bool operator<(const event &p) const {
        return y < p.y;
    }
};

int seg[1 << 19];
void update(int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[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);
    seg[i] = seg[i << 1] + seg[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 seg[i];
    int m = (s + e) / 2;
    return query(i << 1, s, m, x, y) + query(i << 1 | 1, m + 1, e, x, y);
}

pii getVertexEdges(int mx, const vector<line>& ls, const vector<line>& le) {
    int v = 0, e = 0;
    vector<event> ev;
    for (line i : le) {
        ev.push_back({ i.y, i.x1, 1 });
        ev.push_back({ i.y, i.x2 + 1, -1 });
    }
    sort(ev.begin(), ev.end());
    int j = 0;
    for (line i : ls) {
        while (j < ev.size() && ev[j].y <= i.y)
            update(1, 1, mx, ev[j].x, ev[j].c), ++j;
        int ret1 = query(1, 1, mx, i.x1 + 1, i.x2 - 1);
        int ret2 = query(1, 1, mx, i.x1, i.x2);
        v += ret2;
        e += max(ret2 - 1, 0);
    }
    while (j < ev.size())
        update(1, 1, mx, ev[j].x, ev[j].c), ++j;
    return pii(v, e);
}

int delX[100003];
int delY[100003];
int getComponentSize() {
    return 1;
}

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 });
        else ly.push_back({ b, d, a });
        compx.push_back(a);
        compx.push_back(c);
        compy.push_back(b);
        compy.push_back(d);
    }
    lx.push_back({ 0, w, 0 });
    lx.push_back({ 0, w, h });
    ly.push_back({ 0, h, 0 });
    ly.push_back({ 0, h, w });
    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());
    sort(lx.begin(), lx.end());
    sort(ly.begin(), ly.end());
    for (line &i : lx) i.compress(compx, compy);
    for (line &i : ly) i.compress(compy, compx);
    int v, e1, e2;
    tie(v, e1) = getVertexEdges(compx.size(), lx, ly);
    tie(v, e2) = getVertexEdges(compy.size(), ly, lx);
    int e = e1 + e2;
    int c = getComponentSize();
    printf("%d\n", e - v + c);
	return 0;
}

Compilation message

2014_ho_t5.cpp: In function 'pii getVertexEdges(int, const std::vector<line>&, const std::vector<line>&)':
2014_ho_t5.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < ev.size() && ev[j].y <= i.y)
                ~~^~~~~~~~~~~
2014_ho_t5.cpp:73:13: warning: unused variable 'ret1' [-Wunused-variable]
         int ret1 = query(1, 1, mx, i.x1 + 1, i.x2 - 1);
             ^~~~
2014_ho_t5.cpp:78:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (j < ev.size())
            ~~^~~~~~~~~~~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:90: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:94: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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Incorrect 3 ms 724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Incorrect 3 ms 724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 724 KB Output is correct
2 Incorrect 4 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 912 KB Output is correct
2 Correct 6 ms 916 KB Output is correct
3 Correct 27 ms 1944 KB Output is correct
4 Correct 2 ms 1944 KB Output is correct
5 Correct 5 ms 1944 KB Output is correct
6 Correct 366 ms 12936 KB Output is correct
7 Correct 19 ms 12936 KB Output is correct
8 Incorrect 178 ms 14560 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Incorrect 3 ms 724 KB Output isn't correct
7 Halted 0 ms 0 KB -