제출 #1329985

#제출 시각아이디문제언어결과실행 시간메모리
1329985KerimGift Exchange (JOI24_ho_t4)C++20
100 / 100
786 ms98764 KiB
#include <bits/stdc++.h>
using namespace std;

static const int NEG_INF = -1000000000;

// ---------- Fenwick (BIT) for counts + kth ----------
struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n=0){ init(n); }
    void init(int n_) { n=n_; bit.assign(n+1,0); }
    void add(int i,int v){
        for(; i<=n; i+=i&-i) bit[i]+=v;
    }
    int sumPrefix(int i) const{
        int s=0;
        for(; i>0; i-=i&-i) s+=bit[i];
        return s;
    }
    // smallest idx such that prefix sum >= k (k>=1)
    int kth(int k) const{
        int idx=0;
        int pw=1;
        while((pw<<1) <= n) pw <<= 1;
        for(int d=pw; d; d>>=1){
            int ni = idx + d;
            if(ni<=n && bit[ni] < k){
                idx = ni;
                k -= bit[ni];
            }
        }
        return idx+1;
    }
};

// ---------- Segment tree: range max on values [1..M], point update (max) ----------
struct SegMax {
    int n;
    vector<int> st;
    SegMax(int N=0){ init(N); }
    void init(int N){
        n=1;
        while(n<N) n<<=1;
        st.assign(2*n, 0);
    }
    void update(int pos,int val){ // 1-indexed
        int p=(pos-1)+n;
        st[p]=max(st[p], val);
        for(p>>=1;p;p>>=1) st[p]=max(st[p<<1], st[p<<1|1]);
    }
    int query(int l,int r){ // inclusive, 1-indexed
        if(l>r) return 0;
        int L=(l-1)+n, R=(r-1)+n;
        int ans=0;
        while(L<=R){
            if(L&1) ans=max(ans, st[L++]);
            if(!(R&1)) ans=max(ans, st[R--]);
            L>>=1; R>>=1;
        }
        return ans;
    }
};

// ---------- Segment tree: point assign, range max query on starts [1..N] ----------
struct SegPointMax {
    int n;
    vector<int> st;
    SegPointMax(int N=0){ init(N); }
    void init(int N){
        n=1;
        while(n<N) n<<=1;
        st.assign(2*n, NEG_INF);
    }
    void setPoint(int pos,int val){ // 1-indexed
        int p=(pos-1)+n;
        st[p]=val;
        for(p>>=1;p;p>>=1) st[p]=max(st[p<<1], st[p<<1|1]);
    }
    int query(int l,int r){ // inclusive
        if(l>r) return NEG_INF;
        int L=(l-1)+n, R=(r-1)+n;
        int ans=NEG_INF;
        while(L<=R){
            if(L&1) ans=max(ans, st[L++]);
            if(!(R&1)) ans=max(ans, st[R--]);
            L>>=1; R>>=1;
        }
        return ans;
    }
};

// ---------- Compute S[i] = max j<i overlapping i ----------
static vector<int> compute_prev_overlap(const vector<int>& A, const vector<int>& B){
    int N = (int)A.size()-1;
    int M = 2*N;

    vector<int> S(N+1, 0);

    // Case 1: B_i < A_j < A_i  => query A_j in (B_i, A_i)
    SegMax seg(M+2);
    for(int i=1;i<=N;i++){
        int l=B[i]+1, r=A[i]-1;
        if(l<=r) S[i]=max(S[i], seg.query(l,r));
        seg.update(A[i], i);
    }

    // Case 2: B_j < A_i < A_j
    // Sweep x increasing. Maintain active indices j such that B_j < x < A_j.
    // Use adjacency arrays for events at x = B_j+1 (add), x = A_j (remove), x = A_i (query).

    vector<int> headAdd(M+2, -1), headRem(M+2, -1), headQ(M+2, -1);
    vector<int> nxtAdd(N+1), nxtRem(N+1), nxtQ(N+1);

    auto push = [&](vector<int>& head, vector<int>& nxt, int x, int id){
        nxt[id] = head[x];
        head[x] = id;
    };

    for(int i=1;i<=N;i++){
        // FIXED: only meaningful if exists integer x with B_i < x < A_i
        if(B[i]+1 <= A[i]-1){
            push(headAdd, nxtAdd, B[i]+1, i);
            push(headRem, nxtRem, A[i], i);
        }
        push(headQ, nxtQ, A[i], i);
    }

    Fenwick fw(N);
    vector<char> isActive(N+1, 0);

    for(int x=1;x<=M;x++){
        // remove at x (open interval ends at A)
        for(int id=headRem[x]; id!=-1; id=nxtRem[id]){
            if(isActive[id]){
                isActive[id]=0;
                fw.add(id, -1);
            }
        }
        // add at x (open interval begins just after B)
        for(int id=headAdd[x]; id!=-1; id=nxtAdd[id]){
            if(!isActive[id]){
                isActive[id]=1;
                fw.add(id, +1);
            }
        }
        // queries at x
        for(int i=headQ[x]; i!=-1; i=nxtQ[i]){
            int cnt = fw.sumPrefix(i-1);
            if(cnt>0){
                int j = fw.kth(cnt); // predecessor index
                S[i] = max(S[i], j);
            }
        }
    }

    return S;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N+1), B(N+1);
    for(int i=1;i<=N;i++) cin >> A[i];
    for(int i=1;i<=N;i++) cin >> B[i];

    vector<int> S = compute_prev_overlap(A,B);

    // Compute T via reverse trick
    vector<int> Ar(N+1), Br(N+1);
    for(int i=1;i<=N;i++){
        Ar[i]=A[N+1-i];
        Br[i]=B[N+1-i];
    }
    vector<int> Sr = compute_prev_overlap(Ar,Br);

    vector<int> T(N+1, N+1);
    for(int i=1;i<=N;i++){
        int ri = N+1-i;      // index in reversed
        int prev = Sr[ri];   // max < ri in reversed
        if(prev==0) T[i]=N+1;
        else T[i]=N+1-prev;  // maps back to min > i
    }

    int Q;
    cin >> Q;
    vector<vector<pair<int,int>>> queriesAtL(N+2);
    vector<string> ans(Q);

    for(int qi=0; qi<Q; qi++){
        int L,R;
        cin >> L >> R;
        queriesAtL[L].push_back({R, qi});
    }

    // Rectangle for i: L in [S[i]+1, i], R in [i, T[i]-1]
    // For sweep over L:
    //  activate i at L = S[i]+1
    //  deactivate i at L = i+1
    vector<vector<int>> addAt(N+2), remAt(N+2);
    for(int i=1;i<=N;i++){
        int Ladd = S[i] + 1;
        if(Ladd <= i){
            addAt[Ladd].push_back(i);
            if(i+1 <= N) remAt[i+1].push_back(i);
        }
    }

    vector<int> activeEnd(N+1, NEG_INF);
    SegPointMax seg(N);

    for(int L=1; L<=N; L++){
        for(int i: remAt[L]){
            activeEnd[i] = NEG_INF;
            seg.setPoint(i, NEG_INF);
        }
        for(int i: addAt[L]){
            int endR = T[i] - 1;
            activeEnd[i] = endR;
            seg.setPoint(i, endR);
        }

        for(auto [R, qi] : queriesAtL[L]){
            int bestEnd = seg.query(1, R); // max end among starts <= R
            ans[qi] = (bestEnd >= R ? "No" : "Yes");
        }
    }

    for(int i=0;i<Q;i++) cout << ans[i] << "\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...