Submission #521700

#	Time	Username	Problem	Language	Result	Execution time	Memory
521700		inluminas	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3084 ms	258844 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 int lmt=1e6+10;
vector<int>adj[5*lmt];
int a[lmt],mx,tree[5*lmt];
 
void build(int at,int L,int R){
  if(L==R){
    adj[at].push_back(a[L]);
    return;
  }
  int mid=(L+R)>>1;
  build(at*2,L,mid);
  build(at*2+1,mid+1,R);
 
  int res=adj[at*2].back();
  int 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());
}
 
int query(int at,int L,int R,int l,int 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{
      int lo=0,hi=adj[at].size()-1;
      while(hi-lo>1){
        int mid=(lo+hi)>>1;
        if(adj[at][mid]<mx) lo=mid;
        else hi=mid;
      }
      int 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;
    }
  }
  int mid=(L+R)>>1;
  int 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;
 
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  build(1,1,n);
  for(int i=1;i<=m;i++){
    int l,r,k;
    cin>>l>>r>>k;
    int 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