Submission #1148892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148892		Luvidi	Gift Exchange (JOI24_ho_t4)	C++20	0 / 100	264 ms	17840 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5;
int seg[4*maxn];

int upd(int v,int l,int r,int i,int x){
    if(i<l||i>r)return seg[v];
    if(l==r)return seg[v]=x;
    int m=(l+r)/2;
    return seg[v]=min(upd(2*v+1,l,m,i,x),upd(2*v+2,m+1,r,i,x));
}

int qry(int v,int l,int r,int l2,int r2){
    if(l2>r||r2<l)return 1e9;
    if(l2<=l&&r<=r2)return seg[v];
    int m=(l+r)/2;
    return min(qry(2*v+1,l,m,l2,r2),qry(2*v+2,m+1,r,l2,r2));
}

int main(){
    int n;
    cin>>n;
    pair<int,int> a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i].first;
    for(int i=1;i<=n;i++)cin>>a[i].second;
    pair<int,int> dp[n+1][20];
    dp[0][0]={0,1};
    for(int i=1;i<=n;i++){
        int idx=lower_bound(a+1,a+n+1,make_pair(a[i].second,0))-a,x=qry(0,1,n,idx,i-1);
        if(x<i)dp[i][0]={x,1};
        else dp[i][0]={i-1,0};
        upd(0,1,n,i,dp[i][0].first);
    }
    for(int x=1;x<20;x++){
        for(int i=1;i<=n;i++)dp[i][x]={dp[dp[i][x-1].first][x-1].first,dp[i][x-1].second&&dp[dp[i][x-1].first][x-1].second};
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        bool b=1;
        for(int i=19;i>-1;i--)if(dp[r][i].first>=l){
            b&=dp[r][i].second;
            r=dp[r][i].first;
        }
        b&=dp[r][0].first!=r-1;
        if(b)cout<<"Yes\n";
        else cout<<"No\n";
    }
}

• 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