oj.uz

답안 #690927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
690927 2023-01-30T16:45:37 Z yaufung Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 1376 ms 84172 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
    int mn, mx, lazymn, lazymx;
};
vector<node> tr[20];
int bound = 0;
vector<pair<int, int>> B;

void build(int lay, int p, int l, int r) {
    bound = max(bound, p);
    if (l == r) {
        tr[lay][p].mn = B[l].first;
        tr[lay][p].mx = B[l].second;
        tr[lay][p].lazymn = tr[lay][p].lazymx = -1;
        return;
    }
    int mid = (l + r) / 2;
    build(lay, p * 2, l, mid);
    build(lay, p * 2 + 1, mid + 1, r);
    tr[lay][p].mn = min(tr[lay][p * 2].mn, tr[lay][p * 2 + 1].mn);
    tr[lay][p].mx = max(tr[lay][p * 2].mx, tr[lay][p * 2 + 1].mx);
    tr[lay][p].lazymn = tr[lay][p].lazymx = -1;
    return;
}

void push(int lay, int p) {
    if (tr[lay][p].lazymn != -1) {
        int me = tr[lay][p].lazymn;
        if (p * 2 <= bound) {
            if (tr[lay][p * 2].lazymn == -1) tr[lay][p * 2].lazymn = me;
            else tr[lay][p * 2].lazymn = min(tr[lay][p * 2].lazymn, me);
            tr[lay][p * 2].mn = min(tr[lay][p * 2].mn, me);
        }
        if (p * 2 + 1 <= bound) {
            if (tr[lay][p * 2 + 1].lazymn == -1) tr[lay][p * 2 + 1].lazymn = me;
            else tr[lay][p * 2 + 1].lazymn = min(tr[lay][p * 2 + 1].lazymn, me);
            tr[lay][p * 2 + 1].mn = min(tr[lay][p * 2 + 1].mn, me);
        }
        tr[lay][p].lazymn = -1;
    }
    if (tr[lay][p].lazymx != -1) {
        int me = tr[lay][p].lazymx;
        if (p * 2 <= bound) {
            if (tr[lay][p * 2].lazymx == -1) tr[lay][p * 2].lazymx = me;
            else tr[lay][p * 2].lazymx = min(tr[lay][p * 2].lazymx, me);
            tr[lay][p * 2].mx = max(tr[lay][p * 2].mx, me);
        }
        if (p * 2 + 1 <= bound) {
            auto &chlazy = tr[lay][p * 2 + 1].lazymx;
            if (tr[lay][p * 2 + 1].lazymx == -1) tr[lay][p * 2 + 1].lazymx = me;
            else tr[lay][p * 2 + 1].lazymx = min(tr[lay][p * 2 + 1].lazymx, me);
            tr[lay][p * 2 + 1].mx = max(tr[lay][p * 2 + 1].mx, me);
        }
        tr[lay][p].lazymx = -1;
    }
    return;
}

void up(int lay, int p, int l, int r, int x, int y, int num, int mode) {
    // cout << "up lay=" << lay << " l=" << l << " r=" << r << " x=" << x << " y=" << y << " num=" << num << " mode=" << mode << "\n";
    if (x > r || y < l) return;
    push(lay, p);
    if (x <= l && y >= r) {
        if (mode == -1) {
            if (tr[lay][p].lazymn == -1) tr[lay][p].lazymn = num;
            else tr[lay][p].lazymn = min(tr[lay][p].lazymn, num);
            tr[lay][p].mn = min(tr[lay][p].mn, num);
        }
        else {
            if (tr[lay][p].lazymx == -1) tr[lay][p].lazymx = num;
            else tr[lay][p].lazymx = max(tr[lay][p].lazymx, num);
            tr[lay][p].mx = max(tr[lay][p].mx, num);
        }
        // cout << "l=" << l << " r=" << r << " mn=" << tr[lay][p].mn << " mx=" << tr[lay][p].mx << "\n";
        return;
    }
    int mid = (l + r) / 2;
    up(lay, p * 2, l, mid, x, y, num, mode);
    up(lay, p * 2 + 1, mid + 1, r, x, y, num, mode);
    tr[lay][p].mn = min(tr[lay][p * 2].mn, tr[lay][p * 2 + 1].mn);
    tr[lay][p].mx = max(tr[lay][p * 2].mx, tr[lay][p * 2 + 1].mx);
    return;
}

pair<int, int> qu(int lay, int p, int l, int r, int x, int y) {
    if (x > r || y < l) return {1e9, -1};
    push(lay, p);
    if (x <= l && y >= r) {
        return {tr[lay][p].mn, tr[lay][p].mx};
    }
    int mid = (l + r) / 2;
    auto pr1 = qu(lay, p * 2, l, mid, x, y);
    auto pr2 = qu(lay, p * 2 + 1, mid + 1, r, x, y);
    pair<int, int> ans;
    ans.first = min(pr1.first, pr2.first);
    ans.second = max(pr1.second, pr2.second);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    int n, m, k, q, r1, r2;
    cin >> n >> k >> m;
    vector<pair<int, int>> A(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> r1 >> r2;
        A[i] = {r1, r2};
    }
    cin >> q;
    vector<pair<int, int>> Q(q + 1);
    for (int i = 1; i <= q; i++) {
        cin >> r1 >> r2;
        Q[i] = {r1, r2};
    }
    int two = 1, ct = 1;
    while (ct < n) {
        ct *= 2;
        two++;
    }
    for (int i = 0; i <= two; i++) {
        tr[i].reserve(4 * n + 1);
    }
    B.reserve(n + 1);
    for (int i = 1; i <= n; i++) {
        B[i] = {i, i};
    }
    build(0, 1, 1, n);
    for (int i = 1; i <= m; i++) {
        int sl, sr;
        if (A[i].first < A[i].second) {
            sl = A[i].first;
            sr = A[i].first + k - 1;
            up(0, 1, 1, n, sl, sr, A[i].second, 1);
        }
        else {
            sl = A[i].first - k + 1;
            sr = A[i].first;
            up(0, 1, 1, n, sl, sr, A[i].second, -1);
        }
    }
    for (int i = 1; i <= two; i++) {
        int last = i - 1;
        for (int j = 1; j <= n; j++) {
            int l, r;
            auto pr = qu(last, 1, 1, n, j, j);
            l = pr.first;
            r = pr.second;
            pr = qu(last, 1, 1, n, l, r);
            B[j] = pr;
        }
        build(i, 1, 1, n);
    }
    for (int i = 1; i <= q; i++) {
        int ans = 0;
        int l, r;
        l = r = Q[i].first;
        auto pr = qu(two, 1, 1, n, l, r);
        if (Q[i].second < pr.first || Q[i].second > pr.second) {
            ans = -1;
        }
        else {
            for (int j = two - 1; j >= 0; j--) {
                pr = qu(j, 1, 1, n, l, r);
                if (Q[i].second < pr.first || Q[i].second > pr.second) {
                    ans += (1 << j);
                    l = pr.first;
                    r = pr.second;
                }
            }
            ans++;
        }
        cout << ans << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void push(int, int)':
Main.cpp:51:19: warning: unused variable 'chlazy' [-Wunused-variable]
   51 |             auto &chlazy = tr[lay][p * 2 + 1].lazymx;
      |                   ^~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 989 ms 80712 KB Output is correct
2 Correct 877 ms 80756 KB Output is correct
3 Correct 945 ms 80956 KB Output is correct
4 Correct 846 ms 80512 KB Output is correct
5 Correct 929 ms 83112 KB Output is correct
6 Correct 907 ms 83092 KB Output is correct
7 Correct 542 ms 82808 KB Output is correct
8 Correct 540 ms 81132 KB Output is correct
9 Correct 486 ms 81068 KB Output is correct
10 Incorrect 1074 ms 83104 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 960 ms 84172 KB Output is correct
2 Correct 1369 ms 82336 KB Output is correct
3 Correct 1376 ms 81412 KB Output is correct
4 Correct 1318 ms 80904 KB Output is correct
5 Correct 1081 ms 80468 KB Output is correct
6 Correct 1209 ms 80520 KB Output is correct
7 Correct 968 ms 82212 KB Output is correct
8 Incorrect 2 ms 444 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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