Submission #1191053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191053		patgra	Gift Exchange (JOI24_ho_t4)	C++20	10 / 100	118 ms	48720 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int maxn = 5e5 + 7, tb = 1 << 20, maxq = 2e5 + 7;

int n, q;
int a[maxn], b[maxn], lastLeft[maxn], firstRight[maxn];
int tr[2 * tb], lz[2 * tb];
pair<int, int> queries[maxq];
vector<int> queriesAt[maxn], offAt[maxn];
int answers[maxq];

int tMax(int l, int r) {
    l += tb, r += tb;
    auto ans = max(tr[l], tr[r]);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) ans = max(ans, tr[l + 1]);
        if(r % 2 == 1) ans = max(ans, tr[r - 1]);
        l /= 2; r /= 2;
        ans = max(ans, max(lz[l], lz[r]));
    }
    while(l > 1) l /= 2, ans = max(ans, lz[l]);
    return ans;
}

void tSetMax(int l, int r, int x) {
    l += tb; r += tb;
    tr[l] = tr[r] = x;
    while(l / 2 != r / 2) {
        if(l % 2 == 0) tr[l + 1] = lz[l + 1] = x;
        if(r % 2 == 1) tr[r - 1] = lz[r - 1] = x;
        l /= 2; r /= 2;
        tr[l] = max(max(tr[2 * l], tr[2 * l + 1]), lz[l]);
        tr[r] = max(max(tr[2 * r], tr[2 * r + 1]), lz[r]);
    }
    while(l / 2) l /= 2, tr[l] = max(max(tr[2 * l], tr[2 * l + 1]), lz[l]);
}
    
int tMin(int l, int r) {
    l += tb, r += tb;
    auto ans = min(tr[l], tr[r]);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) ans = min(ans, tr[l + 1]);
        if(r % 2 == 1) ans = min(ans, tr[r - 1]);
        l /= 2; r /= 2;
        ans = min(ans, min(lz[l], lz[r]));
    }
    while(l > 1) l /= 2, ans = min(ans, lz[l]);
    return ans;
}

void tSetMin(int l, int r, int x) {
    l += tb; r += tb;
    tr[l] = tr[r] = x;
    while(l / 2 != r / 2) {
        if(l % 2 == 0) tr[l + 1] = lz[l + 1] = x;
        if(r % 2 == 1) tr[r - 1] = lz[r - 1] = x;
        l /= 2; r /= 2;
        tr[l] = min(min(tr[2 * l], tr[2 * l + 1]), lz[l]);
        tr[r] = min(min(tr[2 * r], tr[2 * r + 1]), lz[r]);
    }
    while(l / 2) l /= 2, tr[l] = min(min(tr[2 * l], tr[2 * l + 1]), lz[l]);
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];

    rep(i, 0, 2 * tb) tr[i] = lz[i] = -1;
    rep(i, 0, n) {
        lastLeft[i] = tMax(b[i], a[i]);
        DC << "ll[" << i << "] = " << lastLeft[i] << eol;
        tSetMax(b[i], a[i], i);
    }
    rep(i, 0, 2 * tb) tr[i] = lz[i] = n;
    repD(i, n - 1, -1) {
        firstRight[i] = tMin(b[i], a[i]);
        DC << "fr[" << i << "] = " << firstRight[i] << eol;
        tSetMin(b[i], a[i], i);
    }

    cin >> q;
    rep(i, 0, q) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        queries[i] = {l, r};
        queriesAt[r].pb(i);
    }

    rep(i, 0, 2 * tb) tr[i] = lz[i] = n;
    rep(i, 0, n) tr[i + tb] = lz[i + tb] = lastLeft[i];
    repD(i, tb - 1, 0) tr[i] = max(tr[2 * i], tr[2 * i + 1]);

    rep(i, 0, n) if(firstRight[i] != n) offAt[firstRight[i]].pb(i);

    rep(i, 0, n) {
        repIn(j, offAt[i]) tSetMin(j, j, j);
        repIn(j, queriesAt[i]) answers[j] = tMin(queries[j].first, queries[j].second) >= queries[j].first;
    }

    rep(i, 0, q) cout << (answers[i] ? "Yes\n" : "No\n");
}

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