Submission #1015426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015426		ReLice	Gift Exchange (JOI24_ho_t4)	C++17	100 / 100	1741 ms	168528 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=1e9+7;
const ll N=1e6+7;
const ld eps=1e-9;
struct ST{
    vector<ll> t,add;
    void init(ll id){
        if(id==0)t.assign(N*4,-inf);
        else t.assign(N*4,0);
        add.assign(N*4,0);
    }
    void push(ll id,ll v,ll tl,ll tr){
        if(add[v]==0) return;
        if(tl!=tr){
            if(id==0) add[v*2]=add[v*2+1]=add[v];
            else{
                add[v*2]+=add[v];
                add[v*2+1]+=add[v];
            }
        }
        if(id==0) t[v]=add[v];
        else t[v]+=add[v];
        add[v]=0;
    }
    void ad(ll pos,ll val,ll v=1,ll tl=1,ll tr=N){
        push(1,v,tl,tr);
        if(tl>pos || tr<pos) return;
        if(tl==tr){
            add[v]+=val;
            push(1,v,tl,tr);
            return;
        }ll tm=(tl+tr)/2;
        ad(pos,val,v*2,tl,tm);
        ad(pos,val,v*2+1,tm+1,tr);
        t[v]=t[v*2]+t[v*2+1];
    }
    void ss(ll l,ll r,ll val,ll v=1,ll tl=1,ll tr=N){
        push(0,v,tl,tr);
        if(tl>r || tr<l)return;
        if(l<=tl && tr<=r){
            add[v]=val;
            push(0,v,tl,tr);
            return;
        }ll tm=(tl+tr)/2;
        ss(l,r,val,v*2,tl,tm);
        ss(l,r,val,v*2+1,tm+1,tr);
        t[v]=max(t[v*2],t[v*2+1]);
    }
    ll sum(ll l,ll r,ll v=1,ll tl=1,ll tr=N){
        push(1,v,tl,tr);
        if(tl>r || tr<l)return 0;
        if(l<=tl && tr<=r)return t[v];
        ll tm=(tl+tr)/2;
        return sum(l,r,v*2,tl,tm)+sum(l,r,v*2+1,tm+1,tr);
    }
    ll mx(ll l,ll r,ll v=1,ll tl=1,ll tr=N){
        push(0,v,tl,tr);
        if(tl>r || tr<l) return -inf;
        if(l<=tl && tr<=r) return t[v];
        ll tm=(tl+tr)/2;
        return max(mx(l,r,v*2,tl,tm),mx(l,r,v*2+1,tm+1,tr));
    }
}segtree;
ll a[N],b[N];
ll l[N],r[N];
vector<vll> v(N),vv(N);
ll L[N],R[N];
ll ans[N];
void solve(){
    ll i,j;
    ll n,q;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)cin>>b[i];
    segtree.init(0);
    for(i=1;i<=n;i++){
        l[i]=segtree.mx(b[i],a[i]);
        chmax(l[i],0ll);
        //cout<<l[i]<<' ';
        segtree.ss(b[i],a[i],i);
    }//cout<<endl;
    segtree.init(0);
    for(i=n;i>0;i--){
        r[i]=-segtree.mx(b[i],a[i]);
        chmin(r[i],n+1);
        //cout<<r[i]<<' ';
        segtree.ss(b[i],a[i],-i);
    }//cout<<endl;
    segtree.init(1);
    cin>>q;
    for(i=0;i<q;i++){
        cin>>L[i]>>R[i];
        v[R[i]].pb(i);
    }
    for(i=1;i<=n;i++){
        segtree.ad(l[i],-1);
        segtree.ad(i,1);
        vv[r[i]].pb(i);
        for(auto j : vv[i]){
            segtree.ad(l[j],1);
            segtree.ad(j,-1);
        }
        //for(j=1;j<=i;j++)cout<<segtree.sum(j,j)<<' ';cout<<endl;
        for(auto j : v[i]){
            ans[j]=segtree.sum(L[j],R[j]);
        }
    }
    for(i=0;i<q;i++){
        cout<<(ans[i]==0 ? "Yes" : "No")<<endl;
    }
}
signed main(){
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*
3 100
3 3 3
2
3 3 2
3 3 3



*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:110:10: warning: unused variable 'j' [-Wunused-variable]
  110 |     ll i,j;
      |          ^

• 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