제출 #1236386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236386		wetsponge	Gift Exchange (JOI24_ho_t4)	C++20	88 / 100	313 ms	122108 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define mod 1000000007
int n,k,A[200001],B[200001],L[200001],R[200001],ans[200001];
const int N=(1ll<<20);
int TreeMN[3][N*2+5],TreeMX[3][N*2+5];
int inf=1e18;
vector <array<int,2>> qu[200001];
vector <int> p[200001];
void updateMN(int i,int val,int u){
    i+=N;
    TreeMN[u][i]=val;
    i/=2;
    while(i!=0){
        TreeMN[u][i]=min(TreeMN[u][i*2],TreeMN[u][i*2+1]);
        i/=2;
    }
    return;
}
void updateMX(int i,int val,int u){
    i+=N;
    TreeMX[u][i]=val;
    i/=2;
    while(i!=0){
        TreeMX[u][i]=max(TreeMX[u][i*2],TreeMX[u][i*2+1]);
        i/=2;
    }
    return;
}
int solveMN(int l1,int r1,int i,int l,int r,int u){
    if(l1>r||l>r1) return n+1;
    if(l<=l1&&r1<=r) return TreeMN[u][i];
    return min(solveMN(l1,(l1+r1)/2,i*2,l,r,u),solveMN((l1+r1)/2+1,r1,i*2+1,l,r,u));
}
int solveMX(int l1,int r1,int i,int l,int r,int u){
    if(l1>r||l>r1) return 0;
    if(l<=l1&&r1<=r) return TreeMX[u][i];
    return max(solveMX(l1,(l1+r1)/2,i*2,l,r,u),solveMX((l1+r1)/2+1,r1,i*2+1,l,r,u));
}
int solveMN2(int i,int u){
    i+=N;
    int ans=n+1;
    while(i!=0){
        //cout<<i<<" "<<TreeMN[u][i]<<endl;
        ans=min(ans,TreeMN[u][i]);
        i/=2;
    }
    return ans;
}
int solveMX2(int i,int u){
    i+=N;
    int ans=0;
    while(i!=0){
        ans=max(ans,TreeMX[u][i]);
        i/=2;
    }
    return ans;
}
void updateMN2(int l1,int r1,int i,int l,int r,int u,int val){
    if(l1>r||l>r1) return;
    if(l<=l1&&r1<=r){
        TreeMN[u][i]=min(TreeMN[u][i],val);
        return;
    }
    updateMN2(l1,(l1+r1)/2,i*2,l,r,u,val);
    updateMN2((l1+r1)/2+1,r1,i*2+1,l,r,u,val);
    return;
}
void updateMX2(int l1,int r1,int i,int l,int r,int u,int val){
    if(l1>r||l>r1) return;
    if(l<=l1&&r1<=r){
        TreeMX[u][i]=max(TreeMX[u][i],val);
        return;
    }
    updateMX2(l1,(l1+r1)/2,i*2,l,r,u,val);
    updateMX2((l1+r1)/2+1,r1,i*2+1,l,r,u,val);

    return;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=0;i<=N*2+4;i++){
        TreeMN[0][i]=TreeMN[1][i]=TreeMN[2][i]=n+1;
        TreeMX[0][i]=TreeMX[1][i]=TreeMX[2][i]=0;
    }
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<=n;i++) cin>>B[i];
    for(int i=1;i<=n;i++){
        updateMX(A[i],i,0);
        updateMX(B[i],i,0);
        L[i]=solveMX(0,N-1,1,B[i]+1,A[i]-1,0);
        L[i]=max(L[i],solveMX2(A[i],2));
        updateMX2(0,N-1,1,B[i],A[i],2,i);
    }
    for(int i=n;i>=1;i--){
        updateMN(A[i],i,0);
        updateMN(B[i],i,0);
        R[i]=solveMN(0,N-1,1,B[i]+1,A[i]-1,0);
        //cout<<i<<" "<<solveMN2(A[i],2)<<endl;
        R[i]=min(R[i],solveMN2(A[i],2));
        updateMN2(0,N-1,1,B[i],A[i],2,i);
        p[L[i]].push_back(i);
    }
    //for(int i=1;i<=n;i++) cout<<L[i]<<" "<<R[i]<<endl;
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        qu[l].push_back({r,i});
    }
    for(int l=0;l<=n;l++){
        for(auto [r,idx]:qu[l]){
            if(solveMX(0,N-1,1,l,r,1)<=r) ans[idx]=1;
        }
        for(int idx:p[l]){
            updateMX(idx,R[idx],1);
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i]==1) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

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