제출 #1208996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208996		qilby	Gift Exchange (JOI24_ho_t4)	C++20	88 / 100	2591 ms	280464 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1000009;

struct fenwick {
    vector < int > t;

    fenwick() { t.resize(N, 0); }

    void add(int p, int x) { for (int i = p; i < N; i += (i & -i)) t[i] += x; }

    int get(int p) {
        int res = 0;
        for (int i = p; i >= 1; i -= (i & -i)) res += t[i];
        return res;
    }
};

bool res[N];
vector < int > g[N * 2], h[N * 2];
vector < array < int , 3 > > vec[N];
int n, q, a[N], b[N], lft[N], rgt[N];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        g[v] = {b[tl]}, h[v] = {a[tl]};
        return;
    }

    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);

    int i = 0, j = 0;

    while (i < (int)g[v + v].size() || j < (int)g[v + v + 1].size()) {
        int lg, rg;

        if (j >= (int)g[v + v + 1].size() || (i < (int)g[v + v].size() && h[v + v][i] < h[v + v + 1][j])) { lg = g[v + v][i], rg = h[v + v][i]; i++; }
        else { lg = g[v + v + 1][j], rg = h[v + v + 1][j]; j++; }

        while (i < (int)g[v + v].size() || j < (int)g[v + v + 1].size()) {
            bool was = 0;

            if (i < (int)g[v + v].size()) {
                if (g[v + v][i] < rg) {
                    lg = min(lg, g[v + v][i]);
                    rg = max(rg, h[v + v][i]);
                    i++, was = 1;
                }
            }
            if (j < (int)g[v + v + 1].size()) {
                if (g[v + v + 1][j] < rg) {
                    lg = min(lg, g[v + v + 1][j]);
                    rg = max(rg, h[v + v + 1][j]);
                    j++, was = 1;
                }
            }

            if (!was) break;
        }

        g[v].push_back(lg), h[v].push_back(rg);
    }
}

int getf(int v, int tl, int tr, int l, int r, int lg, int rg) {
    if (tr < l || tl > r || l > r) return n + 1;

    int i = lower_bound(h[v].begin(), h[v].end(), lg) - h[v].begin();
    if (g[v][i] > rg) return n + 1;

    if (tl == tr) return tl;

    int tm = (tl + tr) >> 1;
    int x = getf(v + v, tl, tm, l, r, lg, rg);

    if (x != n + 1) return x;
    return getf(v + v + 1, tm + 1, tr, l, r, lg, rg);
}

int getl(int v, int tl, int tr, int l, int r, int lg, int rg) {
    if (tr < l || tl > r || l > r) return 0;

    int i = lower_bound(h[v].begin(), h[v].end(), lg) - h[v].begin();
    if (g[v][i] > rg) return 0;

    if (tl == tr) return tl;

    int tm = (tl + tr) >> 1;
    int x = getl(v + v + 1, tm + 1, tr, l, r, lg, rg);

    if (x != 0) return x;
    return getl(v + v, tl, tm, l, r, lg, rg);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) cin >> b[i];

    build(1, 1, n);

    for (int i = 1; i <= n * 4; i++) if (!g[i].empty()) {
        g[i].push_back((int)1e9);
        h[i].push_back((int)1e9);
    }

    for (int i = 1; i <= n; i++) {
        lft[i] = getl(1, 1, n, 1, i - 1, b[i], a[i]);
        rgt[i] = getf(1, 1, n, i + 1, n, b[i], a[i]);
        vec[lft[i] + 1].push_back({i, 0, rgt[i] - 1});
        vec[i + 1].push_back({i, -2, rgt[i] - 1});
    }

    cin >> q;

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        vec[l].push_back({r, i, 0});
    }

    fenwick f;

    for (int i = 1; i <= n; i++) {
        for (auto arr : vec[i]) {
            if (arr[1] < 1) f.add(arr[0], arr[1] + 1), f.add(arr[2] + 1, -arr[1] - 1);
            else {
                int x = f.get(arr[0]);
                if (x > 0) res[arr[1]] = 1;
            }
        }
    }

    for (int i = 1; i <= q; i++) cout << (res[i] ? "No" : "Yes") << "\n";
}

/*
5
3 4 6 9 10
1 2 5 7 8
3
1 5
1 2
2 4
*/

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 0 / 12