제출 #1346636

#제출 시각아이디문제언어결과실행 시간메모리
1346636biankGift Exchange (JOI24_ho_t4)C++20
100 / 100
1430 ms58352 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define qforn(i, n) for (i = 0; i < n; i++)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

#define fst first
#define snd second

const int INF = 1e9;

struct SegTree {
    int n;
    vi st, lazy;
    vb lazyFlag;
    SegTree(int _n) {
        n = 1; while (n < _n) n *= 2;
        st.assign(2 * n, -INF);
        lazy.assign(2 * n, 0);
        lazyFlag.assign(2 * n, false);
    }
    void push(int u) {
        if (!lazyFlag[u]) return;
        if (u < n) {
            lazy[2 * u] = lazy[2 * u + 1] = lazy[u];
            lazyFlag[2 * u] = lazyFlag[2 * u + 1] = true;
        }
        st[u] = lazy[u];
        lazyFlag[u] = false;
    }
    void update(int s, int e, int v, int l = 0, int r = -1, int u = 1) {
        if (r == -1) r = n;
        push(u);
        if (e <= l || r <= s) return;
        if (s <= l && r <= e) {
            lazyFlag[u] = true;
            lazy[u] = v;
            return push(u);
        }
        int m = (l + r) / 2;
        update(s, e, v, l, m, 2 * u);
        update(s, e, v, m, r, 2 * u + 1);
        st[u] = max(st[2 * u], st[2 * u + 1]);
    }
    int query(int s, int e, int l = 0, int r = -1, int u = 1) {
        if (r == -1) r = n;
        push(u);
        if (e <= l || r <= s) return -INF;
        if (s <= l && r <= e) return st[u];
        int m = (l + r) / 2;
        return max(query(s, e, l, m, 2 * u), query(s, e, m, r, 2 * u + 1));
    }
};

int main() {
    ios::sync_with_stdio(0);                
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vi a(n), b(n);
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i], --b[i];
    
    int q;
    cin >> q;
    vector<vii> queries(n);
    forn(i, q) {
        int l, r;
        cin >> l >> r;
        --l;
        queries[l].eb(r, i);
    }
    
    SegTree st(2 * n);
    vi l(n), r(n);
    forn(i, n) {
        l[i] = st.query(b[i], a[i]);
        st.update(b[i], a[i], i);
    }
    
    st = SegTree(2 * n);
    dforn(i, n) {
        r[i] = -st.query(b[i], a[i]);
        st.update(b[i], a[i], -i);
    }
    
    
    st = SegTree(2 * n);
    forn(i, n) {
        st.update(i, i + 1, r[i]);
    }
    
    vi order(n);
    iota(all(order), 0);
    sort(all(order), [&](const int &lhs, const int &rhs) {
        return l[lhs] > l[rhs];
    });
    
    int i = 0;
    vb ret(q);
    dforn(L, n) {
        while (i < n && l[order[i]] >= L) {
            int pos = order[i++];
            st.update(pos, pos + 1, -INF);
        }
        for (auto [R, idx] : queries[L]) {
            ret[idx] = st.query(L, R) < R;
        }
    }
    
    forn(i, q) cout << (ret[i] ? "Yes\n" : "No\n");
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...