백준 17975번: Strike Zone [C++]

작성일 | In
다이아몬드 V 다이아몬드 V

문제

Strike Zone

풀이

10167번 금광 문제와 똑같은 풀이를 사용해서 해결할 수 있습니다.

$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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

struct SegmentTree {
    struct Node {
        int sum, lmax, rmax, lrmax;

        void add(int v) { sum = lmax = rmax = lrmax += v; }
    };
    Node merge(const Node& left, const Node& right) {
        Node ret;

        ret.sum = left.sum + right.sum;
        ret.lmax = max(left.lmax, left.sum + right.lmax);
        ret.rmax = max(right.rmax, left.rmax + right.sum);
        ret.lrmax = max({left.rmax + right.lmax, left.lrmax, right.lrmax});

        return ret;
    }

    int n;
    vector<Node> t;

    SegmentTree(int _n) : n(1 << (int)ceil(log2(_n))), t(n << 1) {}

    void reset() { fill(t.begin(), t.end(), Node()); }

    void add(int i, int v) {
        t[i += n].add(v);
        while (i >>= 1)
            t[i] = merge(t[i << 1], t[i << 1 | 1]);
    }

    int getMaxSubArray() { return t[1].lrmax; }
};

struct Point {
    int x, y;
    bool isStrike;
};

Point points[2020];
vector<int> xValues;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n1;
    cin >> n1;
    for (int i = 0; i < n1; i++) {
        auto& [x, y, strike] = points[i];
        strike = true;
        cin >> x >> y;
        xValues.push_back(x);
    }

    int n2;
    cin >> n2;
    int n = n1 + n2;
    for (int i = n1; i < n; i++) {
        auto& [x, y, strike] = points[i];
        strike = false;
        cin >> x >> y;
        xValues.push_back(x);
    }

    int c1, c2;
    cin >> c1 >> c2;

    sort(xValues.begin(), xValues.end());
    xValues.erase(unique(xValues.begin(), xValues.end()), xValues.end());
    for (int i = 0; i < n; i++) {
        int& x = points[i].x;
        x = lower_bound(xValues.begin(), xValues.end(), x) - xValues.begin();
    }

    sort(points, points + n,
         [&](const Point& a, const Point& b) { return a.y < b.y; });

    SegmentTree segTree(xValues.size());
    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0 and points[i].y == points[i - 1].y)
            continue;
        segTree.reset();

        for (int j = i; j < n; j++) {
            segTree.add(points[j].x, points[j].isStrike ? c1 : -c2);

            if (j == n - 1 or points[j].y != points[j + 1].y)
                answer = max(answer, segTree.getMaxSubArray());
        }
    }

    cout << answer;

    return 0;
}

백준 17975번: Strike Zone [C++]