oj.uz

답안 #1046929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046929 2024-08-07T06:24:31 Z 정민찬(#11024) 청소 (JOI20_sweeping) C++17
64 / 100
 9269 ms 1797428 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

struct Node{
    int l, r, val;
};

struct SegmentTree{
    vector<Node> tree;
    void init() {
        tree.clear();
        tree.push_back({-1, -1, -1});
    }
    void update(int node, int s, int e, int l, int r, int val) {
        if (l > e || s > r) return;
        if (l <= s && e <= r) {
            tree[node].val = max(val, tree[node].val);
            return;
        }
        int mid = s + e >> 1;
        if (tree[node].l == -1) {
            tree[node].l = tree.size();
            tree.push_back({-1, -1, -1});
        }
        if (tree[node].r == -1) {
            tree[node].r = tree.size();
            tree.push_back({-1, -1, -1});
        }
        update(tree[node].l, s, mid, l, r, val);
        update(tree[node].r, mid+1, e, l, r, val);
    }
    int query(int node, int s, int e, int tar) {
        if (node == -1) return -1;
        if (s == e) return tree[node].val;
        int mid = s + e >> 1;
        if (tar <= mid) return max(tree[node].val, query(tree[node].l, s, mid, tar));
        return max(tree[node].val, query(tree[node].r, mid+1, e, tar));
    }
};

struct SegmentTree_2D{
    vector<SegmentTree> tree;
    int _N, _M;
    void init(int n, int m) {
        int sz = 1 << __lg(n-1) + 2;
        tree.resize(sz);
        for (int i=1; i<sz; i++) {
            tree[i].init();
        }
        _N = n;
        _M = m;
    };
    void update(int node, int s, int e, int tar, int l, int r, int val) {
        tree[node].update(0, 1, _M, l, r, val);
        if (s == e) return;
        int mid = s + e >> 1;
        if (tar <= mid) update(node*2, s, mid, tar, l, r, val);
        else update(node*2+1, mid+1, e, tar, l, r, val);
    }
    int query(int node, int s, int e, int l, int r, int k) {
        if (l > e || s > r) return 0;
        if (l <= s && e <= r) return tree[node].query(0, 1, _M, k);
        int mid = s + e >> 1;
        return max(query(node*2, s, mid, l, r, k), query(node*2+1, mid+1, e, l, r, k));
    }
};

SegmentTree_2D segX, segY;
SegmentTree segX2, segY2;

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<pair<int,int>> a(M);
    vector<int> X, Y;
    for (int i=0; i<M; i++) {
        cin >> a[i].first >> a[i].second;
        X.push_back(a[i].first);
        Y.push_back(a[i].second);
    }
    vector<array<int,3>> qrs(Q);
    vector<int> X2, Y2;
    for (int i=0; i<Q; i++) {
        cin >> qrs[i][0] >> qrs[i][1];
        if (qrs[i][0] == 4) {
            cin >> qrs[i][2];
            X.push_back(qrs[i][1]);
            Y.push_back(qrs[i][2]);
        }
        else if (qrs[i][0] == 2) {
            X2.push_back(N-qrs[i][1]);
        }
        else if (qrs[i][0] == 3) {
            Y2.push_back(N-qrs[i][1]);
        }
    }
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    sort(Y.begin(), Y.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());
    sort(X2.begin(), X2.end());
    X2.erase(unique(X2.begin(), X2.end()), X2.end());
    sort(Y2.begin(), Y2.end());
    Y2.erase(unique(Y2.begin(), Y2.end()), Y2.end());
    int MX = X.size(), MY = Y.size();
    segX.init(MY, MX);
    segY.init(MX, MY);
    segX2.init();
    segY2.init();
    for (int i=0; i<Q; i++) {
        if (qrs[i][0] == 1) {
            int p = qrs[i][1];
            p --;
            int xi = lower_bound(X.begin(), X.end(), a[p].first) - X.begin() + 1;
            int yi = lower_bound(Y.begin(), Y.end(), a[p].second) - Y.begin() + 1;
            int x = segX.query(1, 1, MY, yi, MY, xi);
            int y = segY.query(1, 1, MX, xi, MX, yi);
            cout << max(a[p].first, x) << ' ' << max(a[p].second, y) << '\n';
        }
        else if (qrs[i][0] == 2) { // H
            int L = qrs[i][1];
            int idx = lower_bound(X2.begin(), X2.end(), N-L) - X2.begin() + 1;
            int lval = segX2.query(0, 1, X2.size(), idx);
            int yi = upper_bound(Y.begin(), Y.end(), L) - Y.begin();
            int li = upper_bound(X.begin(), X.end(), lval) - X.begin() + 1;
            int ri = upper_bound(X.begin(), X.end(), N-L) - X.begin();
            if (yi && li <= ri)
                segX.update(1, 1, MY, yi, li, ri, N-L);
            int li2 = upper_bound(Y2.begin(), Y2.end(), L) - Y2.begin() + 1;
            int ri2 = upper_bound(Y2.begin(), Y2.end(), N-(lval+1)) - Y2.begin();
            if (li2 <= ri2) {
                segY2.update(0, 1, Y2.size(), li2, ri2, L);
            }
        }
        else if (qrs[i][0] == 3) { // V
            int L = qrs[i][1];
            int idx = lower_bound(Y2.begin(), Y2.end(), N-L) - Y2.begin() + 1;
            int lval = segY2.query(0, 1, Y2.size(), idx);
            int xi = upper_bound(X.begin(), X.end(), L) - X.begin();
            int li = upper_bound(Y.begin(), Y.end(), lval) - Y.begin() + 1;
            int ri = upper_bound(Y.begin(), Y.end(), N-L) - Y.begin();
            if (xi && li <= ri)
                segY.update(1, 1, MX, xi, li, ri, N-L);
            int li2 = upper_bound(X2.begin(), X2.end(), L) - X2.begin() + 1;
            int ri2 = upper_bound(X2.begin(), X2.end(), N-(lval+1)) - X2.begin();
            if (li2 <= ri2) {
                segX2.update(0, 1, X2.size(), li2, ri2, L);
            }
        }
        else {
            a.push_back({qrs[i][1], qrs[i][2]});
        }
    }

}

Compilation message

sweeping.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
sweeping.cpp:24:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         int mid = s + e >> 1;
      |                   ~~^~~
sweeping.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
sweeping.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid = s + e >> 1;
      |                   ~~^~~
sweeping.cpp: In member function 'void SegmentTree_2D::init(int, int)':
sweeping.cpp:49:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   49 |         int sz = 1 << __lg(n-1) + 2;
      |                       ~~~~~~~~~~^~~
sweeping.cpp: In member function 'void SegmentTree_2D::update(int, int, int, int, int, int, int)':
sweeping.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid = s + e >> 1;
      |                   ~~^~~
sweeping.cpp: In member function 'int SegmentTree_2D::query(int, int, int, int, int, int)':
sweeping.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6748 ms 1110972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8721 ms 1309288 KB Output is correct
2 Correct 8613 ms 1359488 KB Output is correct
3 Correct 4874 ms 1787356 KB Output is correct
4 Correct 3189 ms 890700 KB Output is correct
5 Correct 7864 ms 1082736 KB Output is correct
6 Correct 8353 ms 1221636 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8721 ms 1309288 KB Output is correct
2 Correct 8613 ms 1359488 KB Output is correct
3 Correct 4874 ms 1787356 KB Output is correct
4 Correct 3189 ms 890700 KB Output is correct
5 Correct 7864 ms 1082736 KB Output is correct
6 Correct 8353 ms 1221636 KB Output is correct
7 Correct 9269 ms 1357652 KB Output is correct
8 Correct 9246 ms 1375476 KB Output is correct
9 Correct 9043 ms 1377572 KB Output is correct
10 Correct 4941 ms 1797428 KB Output is correct
11 Correct 3405 ms 910296 KB Output is correct
12 Correct 8115 ms 1097280 KB Output is correct
13 Correct 7695 ms 1087092 KB Output is correct
14 Correct 92 ms 20152 KB Output is correct
15 Correct 1272 ms 74248 KB Output is correct
16 Correct 8887 ms 1201508 KB Output is correct
17 Correct 8556 ms 1243904 KB Output is correct

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2904 KB Output isn't correct
2 Halted 0 ms 0 KB -