Submission #919572

#	Time	Username	Problem	Language	Result	Execution time	Memory
919572		manizare	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	2492 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ; 
using namespace std ;   
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6+ 10 , maxm = 1e6+10 , lg = 18 , inf= 1e18 , mod = 998244353 ;
int par[maxn] , l[maxn] , ans[maxn ] , a[maxn] , L[maxn] , w[maxn] , mx[4*maxn] ;int n, q ;
vector <int> vec[maxn] , qu[maxn] , up[maxn] ;

int find(int v){
    if(par[v]==0)return v;
    return par[v] = find(par[v]) ;
}
void mrg(int x ,int y){ 
    if(x==y)return ;
    l[y] = l[x] ; 
    par[x] = y ; 
}
void upd(int x ,int w, int p =1 ,int l =1 , int r =n ){
    int mid = (l+r)/2 ,pl = p<< 1, pr =p<<1|1 ;
    if(x > r || l > x){
        return ;
    }
    if(l==r){
        mx[p] = w;
        return ;
    }
    upd(x,w,pl,l,mid);
    upd(x,w,pr,mid+1,r);
    mx[p] = max(mx[pl] , mx[pr]) ;
}
int que(int le, int ri ,int p = 1, int l = 1, int r= n){
    int mid = (l+r)/2 ,pl =p<<1 ,pr = p<<1|1 ;
    if(le > r || l > ri)return -inf;
    if(le <= l && r <= ri){
        return mx[p] ;
    }
    return max(que(le,ri,pl,l,mid),que(le,ri,pr,mid+1,r));
}

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
    cin >> n >> q ;
    vector <int> cm ;
    rep(i , 1, n){
        cin >> a[i] ;
        l[i] = i ;
        cm.pb(a[i]);
    }
    sort(all(cm) );
    cm.resize(unique(all(cm))-cm.begin());
    vector <pii> c ; 
    rep(i , 1, n){
        if(i!=n)c.pb({i,i+1}) ;
        a[i]=lower_bound(all(cm) , a[i]) - cm.begin() ;
        vec[a[i]].pb(i) ;
    }
    a[0] = a[n+1] = inf ;
    rep(i , 0 , sz(cm)-1){
        for(int x : vec[i]){
            if(a[x-1] < a[x]){
                c.pb({l[find(x-1)]-1 , x}) ;
            }
            if(a[x+1] < a[x]){
                c.pb({x,find(x+1)+1}) ;
            }
        }
        for(int x : vec[i]){
            if(a[x-1] <= a[x]){
                mrg(find(x-1) , find(x)) ;
            }
            if(a[x+1] <= a[x]){
                mrg(find(x) , find(x+1)) ;
            }
        }
    }
    vector <pii> c2 ;
    for(pii f : c){
        if(f.F <= 0 || f.S > n || a[f.F] <= a[f.S])continue ;
        up[f.S].pb(f.F) ;
    }
    rep(i , 1, q){
        int r ;
        cin >> L[i] >> r >> w[i]  ; 
        qu[r].pb(i) ;
    }
    rep(i , 1, n){
        for(int x : up[i]){
            upd(x , cm[a[x]] + cm[a[i]]) ;
        }
        for(int id : qu[i]){
            ans[id] = que(L[id] , i) ;
        }
    }
    rep(i ,1 , q){
        if(w[i] >= ans[i]){
            cout << 1 << "\n";
        }else{
            cout << 0 << "\n" ;
        }
    }
}
/*
    
*/

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23