Submission #1166605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166605		thinknoexit	Gift Exchange (JOI24_ho_t4)	C++20	0 / 100	0 ms	324 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 500500;
int a[N], b[N];
int tree[4 * N], lazy[4 * N];
int n;
void build(int now = 1, int l = 1, int r = 2 * n) {
    tree[now] = lazy[now] = 0;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(2 * now, l, mid), build(2 * now + 1, mid + 1, r);
}
void lzy(int now, int l, int r) {
    tree[now] += lazy[now];
    if (l != r) {
        lazy[2 * now] += lazy[now];
        lazy[2 * now + 1] += lazy[now];
    }
    lazy[now] = 0;
}
void update(int ql, int qr, 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) {
        lazy[now]++;
        lzy(now, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(ql, qr, 2 * now, l, mid), update(ql, qr, 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 = 2 * n) {
    lzy(now, l, r);
    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 max(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];
    int q;
    cin >> q;
    while (q--) {
        build();
        int l, r;
        cin >> l >> r;
        for (int i = l;i <= r;i++) {
            update(b[i], a[i]);
        }
        bool ch = 1;
        for (int i = l;i <= r;i++) {
            ch &= (query(b[i], a[i]) > 1);
        }
        if (ch) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

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