제출 #521696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521696		inluminas	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	1056 ms	262148 KiB

sortbooks

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const ll lmt=1e6+10;
vector<ll>adj[4*lmt];
ll a[lmt],mx,tree[4*lmt];

void build(ll at,ll L,ll R){
  if(L==R){
    adj[at].push_back(a[L]);
    return;
  }
  ll mid=(L+R)>>1;
  build(at*2,L,mid);
  build(at*2+1,mid+1,R);

  ll res=adj[at*2].back();
  ll lo=0,hi=adj[at*2+1].size()-1;
  while(hi-lo>1){
    mid=(lo+hi)>>1;
    if(adj[at*2+1][mid]<res) lo=mid;
    else hi=mid;
  }

  tree[at]=max(tree[at*2],tree[at*2+1]);

  if(adj[at*2+1][hi]<res) tree[at]=max(tree[at],res+adj[at*2+1][hi]);
  else if(adj[at*2+1][lo]<res) tree[at]=max(tree[at],res+adj[at*2+1][lo]);

  adj[at]=adj[at*2];
  adj[at].insert(adj[at].end(),adj[at*2+1].begin(),adj[at*2+1].end());
  sort(adj[at].begin(),adj[at].end());
}

ll query(ll at,ll L,ll R,ll l,ll r){
  if(r<L || R<l || r<l) return 0;
  if(l<=L && R<=r){
    if(L==l){
      mx=max(mx,adj[at].back());
      return tree[at];
    }else if(adj[at][0]>=mx){
      mx=max(mx,adj[at].back());
      return tree[at];
    }else{
      ll lo=0,hi=adj[at].size()-1;
      while(hi-lo>1){
        ll mid=(lo+hi)>>1;
        if(adj[at][mid]<mx) lo=mid;
        else hi=mid;
      }
      ll res=tree[at];
      if(adj[at][hi]<mx){
        res=max(res,mx+adj[at][hi]);
      }else if(adj[at][lo]<mx){
        res=max(res,mx+adj[at][lo]);
      }
      mx=max(mx,adj[at].back());
      return res;
    }
  }
  ll mid=(L+R)>>1;
  ll x=query(at*2,L,mid,l,r),y=query(at*2+1,mid+1,R,l,r);
  return max(x,y);
}

int main(){
  fastio;

  ll n,m;
  cin>>n>>m;
  for(ll i=1;i<=n;i++){
    cin>>a[i];
  }
  build(1,1,n);
  for(ll i=1;i<=m;i++){
    ll l,r,k;
    cin>>l>>r>>k;
    ll res=query(1,1,n,l,r);
    bool ans=(k>=res);
    cout<<ans<<endl;
    mx=0;
  }
  return 0;
}

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