티스토리 뷰

알고리즘 관련/BOJ

BOJ)2370 시장 선거 포스터

JASON 자손9319 2017. 8. 21. 14:46

문제:icpc.me/2370


포스터를 붙이는 순서가 주어질 때 보이는 포스터의 수를 출력하는 문제이다.


포스터의 모든 x좌표와 y좌표를 좌표압축 한 뒤 


포스터를 역순으로 보면서 이미 본 포스터는 업데이트 시켜주고 내가 보이는지 여부는 이미 업데이트 된 포스터들이 나를 완전히 가리는지 확인하면 된다.


이는 세그먼트 트리를 이용하여 업데이트 된 구간의 합을 찍어냄으로 판별 가능 하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, seg[80040], lazy[80040], res;
pair<intint> qry[10010];
vector<int> v;
int getx(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void u_lazy(int node, int x, int y) {
    if (!lazy[node])
        return;
    seg[node] = (y - x + 1);
    if (x != y) {
        lazy[node * 2= 1;
        lazy[node * + 1= 1;
    }
    lazy[node] = 0;
}
int update(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)return seg[node];
    if (lo <= x&&<= hi) {
        lazy[node] = 1;
        u_lazy(node, x, y);
        return seg[node];
    }
    int mid = (x + y) >> 1;
    return seg[node] = update(lo, hi, node * 2, x, mid) + update(lo, hi, node * + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)return 0;
    if (lo <= x&&<= hi)return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d"&qry[i].first, &qry[i].second);
        v.push_back(qry[i].first);
        v.push_back(qry[i].second);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = n - 1; i >= 0; i--) {
        int l = getx(qry[i].first);
        int r = getx(qry[i].second);
        int getsum = query(l, r, 11* n);
        if (getsum != r - l + 1)res++;
        update(l, r, 11* n);
    }
    printf("%d\n", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13548 수열과 쿼리 6  (0) 2017.09.03
BOJ)2419 사수아탕  (0) 2017.08.27
BOJ)2370 시장 선거 포스터  (1) 2017.08.21
BOJ)3073 집으로 가는 길  (0) 2017.08.21
BOJ)2104 부분배열 고르기  (0) 2017.08.20
BOJ)2872 우리집엔 도서관이 있어  (0) 2017.08.20
댓글
댓글쓰기 폼