Submission #1134037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134037		noyancanturk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1846 ms	75656 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

struct Node{
  int val=0,pri=0,l=0,r=0;
};

Node tree[4000000];

int last=1;
int newnode(int val){
  tree[last].val=val;
  tree[last].pri=rand();
  tree[last].l=tree[last].r=0;
  return last++;
}
int newnode(int val,int pri,int l,int r){
  tree[last].val=val;
  tree[last].pri=pri;
  tree[last].l=l;
  tree[last].r=r;
  return last++;
}
int merge(int l,int r){
  if(!l){
    return r;
  }
  if(!r){
    return l;
  }
  if(tree[r].pri<tree[l].pri){
    return newnode(tree[l].val,tree[l].pri,tree[l].l,merge(tree[l].r,r));
  }else{
    return newnode(tree[r].val,tree[r].pri,merge(l,tree[r].l),tree[r].r);
  }
}
int TRVAL,TRANS;
void query(int node){
  if(!node)return;
  if(tree[node].val<TRVAL){
    TRANS=tree[node].val;
    query(tree[node].r);
  }else{
    query(tree[node].l);
  }
}
int query(int node,int val){
  TRVAL=val,TRANS=-1;
  query(node);
  return TRANS;
}

struct{
  struct stNode{
    int ans,maxval,trnode;
  }tree[4000000];
  stNode merge(stNode n1,stNode n2){
    if(n1.ans==INT_MIN)return n2;
    if(n2.ans==INT_MIN)return n1;
    stNode res;
    int guy=::query(n2.trnode,n1.maxval);
    res.ans=max(n1.ans,n2.ans);
    if(guy!=-1)res.ans=max(res.ans,n1.maxval+guy);
    res.maxval=max(n1.maxval,n2.maxval);
    res.trnode=::merge(n1.trnode,n2.trnode);
    return res;
  }
  int*A,N;
  void build(int l,int r,int node){
    if(l==r){
      tree[node].ans=0;
      tree[node].maxval=A[l];
      tree[node].trnode=newnode(A[l]);
      return;
    }
    int mid=l+r>>1,child=node<<1;
    build(l,mid,child),build(mid+1,r,child|1);
    tree[node]=merge(tree[child],tree[child|1]);
  }
  void build(int*a,int n){
    tree[0]={INT_MIN,INT_MIN,INT_MIN};
    A=a,N=n;
    build(1,N,1);
  }
  int L,R;
  stNode query(int l,int r,int node){
    if(L<=l&&r<=R)return tree[node];
    if(r<L||R<l)return tree[0];
    int mid=l+r>>1,child=node>>1;
    return merge(query(l,mid,child),query(mid+1,r,child|1));
  }
  int query(int l,int r){
    int checkpoint=last;
    L=l,R=r;
    stNode res=query(1,N,1);
    for(int i=checkpoint;i<last;i++){
      ::tree[i].val=::tree[i].pri=::tree[i].l=::tree[i].r=0;
    }
    last=checkpoint;
    return res.ans;
  }
}st;

int main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,m;
  cin>>n>>m;
  int a[n+1];
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  st.build(a,n);
  for(int i=0;i<m;i++){
    int l,r,k;
    cin>>l>>r>>k;
    int res=st.query(l,r);
    cout<<int(res<=k)<<'\n';
  }
}

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