Submission #1188641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188641		user736482	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1251 ms	67896 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops","inline")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define POT (1<<21)
ll a,b,r,c,t,n,m,l,q,k,ak,ans[200007],s;
ll moj[500007],chce[500007],pier[500007],ost[500007];
ll sgtree[POT][2];
vector<pair<pair<ll,ll>,ll>>op;
vector<pair<ll,ll>>op2;
void spych(ll v){
    sgtree[v*2][1]=max(sgtree[v*2][1],sgtree[v][1]);
    sgtree[v*2+1][1]=max(sgtree[v*2+1][1],sgtree[v][1]);
    sgtree[v*2][0]=max(sgtree[v*2][0],sgtree[v*2][1]);
    sgtree[v*2+1][0]=max(sgtree[v*2+1][0],sgtree[v*2+1][1]);
    sgtree[v][1]=-INFL;
}

ll mx(ll pocz,ll kon,ll l,ll r,ll v){
    if(l>kon || r<pocz)return -INFL;
    if(pocz<=l && kon>=r)return sgtree[v][0];
    spych(v);
    return max(mx(pocz,kon,l,(l+r)/2,v*2),mx(pocz,kon,(l+r)/2+1,r,v*2+1));
}




void mn(ll pocz,ll kon,ll l,ll r,ll v,ll val){
    if(l>kon || r<pocz)return;
    if(pocz<=l && kon>=r){sgtree[v][1]=max(sgtree[v][1],val);sgtree[v][0]=max(sgtree[v][0],sgtree[v][1]);return;}
    spych(v);
    mn(pocz,kon,l,(l+r)/2,v*2,val);
    mn(pocz,kon,(l+r)/2+1,r,v*2+1,val);
    sgtree[v][0]=max(sgtree[v*2][0],sgtree[v*2+1][0]);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>moj[i];
    }
    for(ll i=0;i<n;i++){
        cin>>chce[i];
    }
    for(ll i=1;i<POT;i++){
        sgtree[i][0]=-INFL;
        sgtree[i][1]=-INFL;
    }
    for(ll i=0;i<n;i++){
        pier[i]=mx(chce[i],moj[i],1,POT/2,1);
        mn(chce[i],moj[i],1,POT/2,1,i);
    }
    reverse(chce,chce+n);
    reverse(moj,moj+n);
    for(ll i=1;i<POT;i++){
        sgtree[i][0]=-INFL;
        sgtree[i][1]=-INFL;
    }
    for(ll i=0;i<n;i++){
        ost[n-i-1]=n-1-mx(chce[i],moj[i],1,POT/2,1);
        mn(chce[i],moj[i],1,POT/2,1,i);
    }
    for(ll i=1;i<POT;i++){
        sgtree[i][0]=-INFL;
        sgtree[i][1]=-INFL;
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        op.pb({{a-1,b-1},i});
    }
    for(ll i=0;i<n;i++)op2.pb({pier[i]+1,i});
    sort(op.begin(),op.end());
    sort(op2.begin(),op2.end());
    reverse(op.begin(),op.end());
    reverse(op2.begin(),op2.end());
    for(ll i=0;i<n;i++){
        while(op2.size() && op2.back().ff<=i){
            mn(op2.back().ss+1,op2.back().ss+1,1,POT/2,1,ost[op2.back().ss]);
            op2.pop_back();
        }
        while(op.size() && op.back().ff.ff==i){
            ans[op.back().ss]=(mx(op.back().ff.ff+1,op.back().ff.ss+1,1,POT/2,1)<=op.back().ff.ss);
            op.pop_back();
        }
    }
    for(ll i=0;i<q;i++)if(ans[i])cout<<"Yes\n";else cout<<"No\n";
    return 0;
}

• 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