Submission #1154159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154159		irmuun	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1424 ms	46668 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct LazySegMax{
    int n;
    vector<int>d,lazy;
    LazySegMax(int n):n(n){
        d.resize(4*n);
        lazy.resize(4*n);
    }
    void push(int v){
        d[v<<1]=max(d[v<<1],lazy[v]);
        lazy[v<<1]=max(lazy[v<<1],lazy[v]);
        d[v<<1|1]=max(d[v<<1|1],lazy[v]);
        lazy[v<<1|1]=max(lazy[v<<1|1],lazy[v]);
        lazy[v]=0;
    }
    int query(int v,int l,int r,int L,int R){
        if(R<L||R<l||r<L) return 0;
        if(L<=l&&r<=R){
            return d[v];
        }
        push(v);
        int m=(l+r)>>1;
        return max(query(v<<1,l,m,L,R),query(v<<1|1,m+1,r,L,R));
    }
    void update(int v,int l,int r,int L,int R,int val){
        if(R<L||R<l||r<L) return;
        if(L<=l&&r<=R){
            d[v]=val;
            lazy[v]=val;
            return;
        }
        push(v);
        int m=(l+r)>>1;
        update(v<<1,l,m,L,R,val);
        update(v<<1|1,m+1,r,L,R,val);
        d[v]=max(d[v<<1],d[v<<1|1]);
    }
};

struct LazySegMin{
    int n;
    vector<int>d,lazy;
    LazySegMin(int n):n(n){
        d.resize(4*n);
        lazy.resize(4*n);
        fill(all(d),n+1);
        fill(all(lazy),n+1);
    }
    void push(int v){
        //cout<<"pushed "<<v<<"\n";
        d[v<<1]=min(d[v<<1],lazy[v]);
        lazy[v<<1]=min(lazy[v<<1],lazy[v]);
        d[v<<1|1]=min(d[v<<1|1],lazy[v]);
        lazy[v<<1|1]=min(lazy[v<<1|1],lazy[v]);
        lazy[v]=n+1;
    }
    int query(int v,int l,int r,int L,int R){
        if(R<L||R<l||r<L) return n+1;
        if(L<=l&&r<=R){
            return d[v];
        }
        push(v);
        int m=(l+r)>>1;
        return min(query(v<<1,l,m,L,R),query(v<<1|1,m+1,r,L,R));
    }
    void update(int v,int l,int r,int L,int R,int val){
        if(R<L||R<l||r<L) return;
        if(L<=l&&r<=R){
            d[v]=val;
            lazy[v]=val;
            return;
        }
        push(v);
        int m=(l+r)>>1;
        update(v<<1,l,m,L,R,val);
        update(v<<1|1,m+1,r,L,R,val);
        d[v]=min(d[v<<1],d[v<<1|1]);
    }
};

struct segtree{
    int n;
    vector<int>d;
    segtree(int n):n(n){
        d.resize(4*n);
    }
    int query(int v,int l,int r,int L,int R){
        if(R<L||R<l||r<L) return 0;
        if(L<=l&&r<=R){
            return d[v];
        }
        int m=(l+r)>>1;
        return max(query(v<<1,l,m,L,R),query(v<<1|1,m+1,r,L,R));
    }
    void update(int v,int l,int r,int pos,int val){
        if(r<pos||pos<l) return;
        if(l==r){
            d[v]=val;
            return;
        }
        int m=(l+r)>>1;
        update(v<<1,l,m,pos,val);
        update(v<<1|1,m+1,r,pos,val);
        d[v]=max(d[v<<1],d[v<<1|1]);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    int a[n+5],b[n+5];
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    for(ll i=1;i<=n;i++){
        cin>>b[i];
    }
    int s[n+5];
    {
        LazySegMax sg(2*n);
        for(int i=1;i<=n;i++){
            s[i]=sg.query(1,1,2*n,b[i],a[i]);
            sg.update(1,1,2*n,b[i],a[i],i);
        }
    }
    int t[n+5];
    {
        LazySegMin sg(2*n);
        for(int i=n;i>=1;i--){
            t[i]=sg.query(1,1,2*n,b[i],a[i]);
            sg.update(1,1,2*n,b[i],a[i],i);
            if(t[i]>n+1) t[i]=n+1; //lazy
        }
    }
    int q;
    cin>>q;
    int l[q+5],r[q+5];
    for(int i=1;i<=q;i++){
        cin>>l[i]>>r[i];
    }
    int order[q+5];
    iota(order+1,order+q+1,1);
    sort(order+1,order+q+1,[&](int i,int j) {
        return l[i]<l[j];
    });
    segtree sg(n);
    vector<int>add[n+5];
    for(int i=1;i<=n;i++){
        add[s[i]].pb(i);
    }
    int c=0,d=1;
    vector<bool>ans(q+5,1);
    for(int j=1;j<=q;j++){
        int L=l[order[j]],R=r[order[j]];
        while(c<L){
            for(int i:add[c]){
                sg.update(1,1,n,i,t[i]);
            }
            c++;
        }
        while(d<L){
            sg.update(1,1,n,d,0);
            d++;
        }
        if(sg.query(1,1,n,L,R)>R){
            ans[order[j]]=false;
        }
        else{
            ans[order[j]]=true;
        }
    }
    for(int i=1;i<=q;i++){
        cout<<(ans[i]?"Yes\n":"No\n");
    }
}

• 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: 12 / 12