제출 #1166791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166791		thinknoexit	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1329 ms	88788 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 500005;
// precompute
//--------------------
int tree1[8 * N], lazy1[8 * N];
int a[N], b[N], L[N], R[N], n;
bool SS_ = 0;
int op(int a, int b) {
    if (SS_) return min(a, b);
    return max(a, b);
}
void lzy(int now, int l, int r) {
    if (lazy1[now] == 0 || lazy1[now] >= 1e9) return;
    tree1[now] = op(tree1[now], lazy1[now]);
    if (l != r) {
        lazy1[2 * now] = op(lazy1[2 * now], lazy1[now]);
        lazy1[2 * now + 1] = op(lazy1[2 * now + 1], lazy1[now]);
    }
    if (SS_) lazy1[now] = 1e9;
    else lazy1[now] = 0;
}
void update1(int ql, int qr, int w, int now = 1, int l = 1, int r = 2 * n) {
    lzy(now, l, r);
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
        lazy1[now] = w;
        lzy(now, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update1(ql, qr, w, 2 * now, l, mid), update1(ql, qr, w, 2 * now + 1, mid + 1, r);
    tree1[now] = op(tree1[2 * now], tree1[2 * now + 1]);
}
int query1(int ql, int qr, int now = 1, int l = 1, int r = 2 * n) {
    lzy(now, l, r);
    if (ql <= l && r <= qr) return tree1[now];
    int mid = (l + r) / 2;
    if (qr <= mid) return query1(ql, qr, 2 * now, l, mid);
    if (ql > mid) return query1(ql, qr, 2 * now + 1, mid + 1, r);
    return op(query1(ql, qr, 2 * now, l, mid), query1(ql, qr, 2 * now + 1, mid + 1, r));
}
//-------------------------
bool ans[N];
vector<pair<int, int>> Q[N];
vector<int> dis[N];
int tree[4 * N];
void build(int now = 1, int l = 1, int r = n) {
    if (l == r) {
        tree[now] = L[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * now, l, mid), build(2 * now + 1, mid + 1, r);
    tree[now] = min(tree[2 * now], tree[2 * now + 1]);
}
void update(int v, int now = 1, int l = 1, int r = n) {
    if (l == r) {
        tree[now] = 1e9;
        return;
    }
    int mid = (l + r) / 2;
    if (v <= mid) update(v, 2 * now, l, mid);
    else update(v, 2 * now + 1, mid + 1, r);
    tree[now] = min(tree[2 * now], tree[2 * now + 1]);
}
int query(int ql, int qr, int now = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) return tree[now];
    int mid = (l + r) / 2;
    if (qr <= mid) return query(ql, qr, 2 * now, l, mid);
    if (ql > mid) return query(ql, qr, 2 * now + 1, mid + 1, r);
    return min(query(ql, qr, 2 * now, l, mid), query(ql, qr, 2 * now + 1, mid + 1, r));
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    for (int i = 1;i <= n;i++) {
        L[i] = query1(b[i], a[i]);
        update1(b[i], a[i], i);
    }
    memset(tree1, 0x3f, sizeof tree1);
    memset(lazy1, 0x3f, sizeof lazy1);
    SS_ = 1;
    for (int i = n;i >= 1;i--) {
        R[i] = min(n + 1, query1(b[i], a[i]));
        update1(b[i], a[i], i);
    }
    for (int i = 1;i <= n;i++) {
        //cout << L[i] << ' ' << R[i] << '\n';
        dis[R[i]].push_back(i);
    }

    build();
    int q;
    cin >> q;
    for (int i = 1;i <= q;i++) {
        int l, r;
        cin >> l >> r;
        Q[r].push_back({ l, i });
    }
    for (int i = 1;i <= n;i++) {
        for (auto& x : dis[i]) {
            update(x);
        }
        for (auto& [l, idx] : Q[i]) {
            ans[idx] = query(l, i) >= l;
        }
    }
    for (int i = 1;i <= q;i++) {
        if (ans[i]) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

/*
Q:
1 3
1 4
3 4
------
0 3
0 4
1 4
3 5
*/

• 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: 12 / 12