Submission #1209001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209001		qilby	Gift Exchange (JOI24_ho_t4)	C++20	88 / 100	2592 ms	218948 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 < array < int , 3 > > vec[N];
int n, q, a[N], b[N], lft[N], rgt[N];
vector < array < int , 2 > > t[N * 2];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = {{b[tl], 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)t[v + v].size() || j < (int)t[v + v + 1].size()) {
        array < int , 2 > s;

        if (j >= (int)t[v + v + 1].size() || (i < (int)t[v + v].size() && t[v + v][i][1] < t[v + v + 1][j][1])) s = t[v + v][i++];
        else s = t[v + v + 1][j++];

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

            if (i < (int)t[v + v].size()) {
                if (t[v + v][i][0] < s[1]) {
                    s[0] = min(s[0], t[v + v][i][0]);
                    s[1] = max(s[1], t[v + v][i][1]);
                    i++, was = 1;
                }
            }
            if (j < (int)t[v + v + 1].size()) {
                if (t[v + v + 1][j][0] < s[1]) {
                    s[0] = min(s[0], t[v + v + 1][j][0]);
                    s[1] = max(s[1], t[v + v + 1][j][1]);
                    j++, was = 1;
                }
            }

            if (!was) break;
        }

        t[v].push_back(s);
    }
}

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(t[v].begin(), t[v].end(), array < int , 2 >{lg, 0}) - t[v].begin();
    if (t[v][i][1] > 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(t[v].begin(), t[v].end(), array < int , 2 >{lg, 0}) - t[v].begin();
    if (t[v][i][1] > 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++) for (auto &pr : t[i]) swap(pr[0], pr[1]);
    for (int i = 1; i <= n * 4; i++) if (!t[i].empty()) t[i].push_back({(int)1e9, (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