Submission #480333

#	Time	Username	Problem	Language	Result	Execution time	Memory
480333		Ronin13	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1482 ms	107416 KiB

sortbooks

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pll pair<ll,ll>
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define epb emplace back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;
const int NMAX=1e6+1;
int t[4*NMAX];

void update(int v,int l,int r,int pos,int val){
    if(l>pos||r<pos)return;
    if(l==r){
        t[v]=val;
        return;
    }
    int m=(l+r)/2;
    update(2*v,l,m,pos,val);update(2*v+1,m+1,r,pos,val);
    t[v]=max(t[2*v],t[2*v+1]);
}

int get(int v,int l,int r,int st,int fin){
    if(l>fin||r<st)return 0;
    if(l>=st&&r<=fin){
        return t[v];
    }
    int m=(l+r)/2;
    int x=get(2*v,l,m,st,fin);
    int y=get(2*v+1,m+1,r,st,fin);
    return max(x,y);
}

void solve(){
    int n;cin>>n;
    int m;cin>>m;
    vector<vector<int> >vec(n+1);
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    stack<int>st;
    for(int i=1;i<=n;i++){
        while(!st.empty()){
            int v=st.top();
            if(a[v]<=a[i])st.pop();
            else break;
        }
        if(!st.empty()){
            int x=st.top();
            vec[x].pb(i);
        }
        st.push(i);
    }
    vector<pair<pii,pii> >q;
    for(int i=1;i<=m;i++){
        int l,r,x;cin>>l>>r>>x;
        q.pb({{-l,r},{x,i}});
    }
    sort(q.begin(),q.end());
    vector<int>ans(m+1);
    int ind=0;
    for(int i=n;i>=1;i--){
        for(int to:vec[i]){
            update(1,1,n,to,a[to]+a[i]);
        }
        while(ind<m){
            int l=-q[ind].f.f;
            if(l!=i)break;
            int r=q[ind].f.s;
            int val=q[ind].s.f;
            int idx=q[ind].s.s;
            int x=get(1,1,n,l,r);
            if(x>val)ans[idx]=0;
            else ans[idx]=1;
            ind++;
        }
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    int test=1;//cin>>test;
    while(test--){
        solve();
    }
}

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