Submission #1343937

#TimeUsernameProblemLanguageResultExecution timeMemory
1343937vtnooGift Exchange (JOI24_ho_t4)C++20
100 / 100
1391 ms70900 KiB
#include <bits/stdc++.h>
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;
typedef long long ll; 

const int INF=1e9;

//Basicamente necesito saber si algun intervalo me queda "aislado"
//Toma en cuenta que los intervalos pueden ser resueltos offline
//Si calculas para cada intervalo i, el Primero que intersecta a la derecha y izquierda
//Entonces te queda un rango en el cuál si j pertenece a (S_i,T_i) entonces i no se intersecta con j

vector<int>s,t;

struct STreeMax{
    int N;
    vector<pair<int,int>>st;
    STreeMax(int n){
        N=n;
        st.resize(n*4);
    }
    void apply(int v,int x){
        st[v].first=st[v].second=x;
    }
    void push(int v,int s,int e){
        if(!st[v].second||s==e)return;
        apply(v*2,st[v].second);
        apply(v*2+1,st[v].second);
        st[v].second=0;
    }
    void upd(int ts,int te,int x,int v,int s,int e){
        if(e<ts||s>te)return;
        push(v,s,e);
        if(ts<=s&&e<=te){
            apply(v,x);
            return;
        }
        int m=(s+e)/2;
        upd(ts,te,x,v*2,s,m);
        upd(ts,te,x,v*2+1,m+1,e);
        st[v].first=max(st[v*2].first,st[v*2+1].first);
    }
    int que(int ts,int te,int v,int s,int e){
        if(e<ts||s>te)return -1;
        push(v,s,e);
        if(ts<=s&&e<=te){
            return st[v].first;
        }
        int m=(s+e)/2;
        return max(que(ts,te,v*2,s,m),que(ts,te,v*2+1,m+1,e));
    }
    void upd(int ts,int te,int x){upd(ts,te,x,1,1,N);}
    int que(int ts,int te){return que(ts,te,1,1,N);}
};

struct STreeMin{
    int N;
    vector<int>st;
    STreeMin(int n){
        N=n;
        st.resize(n*4);
    }
    void build(vector<int>&a,int v,int s,int e){
        if(s==e)st[v]=a[s-1];
        else{
            int m=(s+e)/2;
            build(a,v*2,s,m);
            build(a,v*2+1,m+1,e); 
            st[v]=min(st[v*2],st[v*2+1]);
        }
    }
    void upd(int ts,int te,int x,int v,int s,int e){
        if(e<ts||s>te)return;
        if(ts<=s&&e<=te){
            st[v]=x;
            return;
        }
        int m=(s+e)/2;
        upd(ts,te,x,v*2,s,m);
        upd(ts,te,x,v*2+1,m+1,e);
        st[v]=min(st[v*2],st[v*2+1]);
    }
    int que(int ts,int te,int v,int s,int e){
        if(e<ts||s>te)return INF;
        if(ts<=s&&e<=te){
            return st[v];
        }
        int m=(s+e)/2;
        return min(que(ts,te,v*2,s,m),que(ts,te,v*2+1,m+1,e));
    }
    void upd(int ts,int te,int x){upd(ts,te,x,1,1,N);}
    int que(int ts,int te){return que(ts,te,1,1,N);}
    void build(vector<int>&a){build(a,1,1,N);}
};

void get_closest(int n,vector<int>&a,vector<int>&b){
    s.resize(n),t.resize(n);
    STreeMax ranges(n*2),ranges2(n*2);
    L(i,0,n-1){
        int closest=ranges.que(b[i],a[i]);
        s[i]=closest;
        ranges.upd(b[i],a[i],i+1);
    }
    R(i,n-1,0){
        int closest=ranges2.que(b[i],a[i]);
        t[i]=closest;
        ranges2.upd(b[i],a[i],n-i);
    }
    L(i,0,n-1){
        if(t[i]==0){
            t[i]=n+1;
        }else t[i]=n-t[i]+1;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;cin>>n;
    vector<int>a(n),b(n);
    L(i,0,n-1)cin>>a[i];
    L(i,0,n-1)cin>>b[i];
    get_closest(n,a,b);
    int q;cin>>q;
    vector<vector<pair<int,int>>>queries(n+1);  
    L(i,0,q-1){
        int l,r;cin>>l>>r;
        queries[r].pb({l,i});
    }
    STreeMin active(n);
    active.build(s);
    vector<vector<int>>trash(n+1); 
    vector<bool>ans(q);
    L(i,1,n){
        for(auto x:trash[i]){
            active.upd(x,x,INF);
        }
        if(t[i-1]<=n)trash[t[i-1]].pb(i);
        sort(all(queries[i]));
        for(auto [l,qi]:queries[i]){
            int lower=active.que(l,i);
            if(lower<l){
                ans[qi]=0;
            }else ans[qi]=1;
        }
    }
    L(i,0,q-1){
        if(ans[i])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}
#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...