Submission #1184437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184437		zhamshid	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	17 / 100	843 ms	33600 KiB

sortbooks

#include <bits/stdc++.h>
#define noSuccess t--
#define int long long
#define pb push_back 
#define F first	
#define S second
#define Sattar_is_the_best ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(s) s.begin(),s.end()
#define yes "YES\n"
#define no "NO\n"
#define sz size
 
using namespace std;
const int maxn = 2e6;
const int mod = 1e9 + 7;
int n,q,a[maxn];
int t[maxn];
int p[maxn];
int get(int v,int tl,int tr,int l,int r){
  if(tl>r || tr<l) return 0;
  if(l<=tl && tr<=r) return t[v];
  int mid = tl + tr >>1;
  return max(get(v+v,tl,mid,l,r),get(v+v+1,mid+1,tr,l,r));
}
void build(int v,int l,int r){
  if(l==r){
    t[v]=p[l];
    return;
  }
  int mid = l + r >> 1;
  build(v+v,l,mid);
  build(v+v+1,mid+1,r);
  t[v]=max(t[v+v],t[v+v+1]);
}
void tryAgain(){
  cin>>n>>q;
  int mn=INT_MAX;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    mn=min(mn,a[i]);
  }
  for(int i=2;i<=n;i++){
    if(a[i]<a[i-1]) p[i]=1;
  }
  build(1,1,n);
  if(n>5000 && q>5000){
    while(q--){
      int l,r,k;
      cin>>l>>r>>k;
      cout<<abs(get(1,1,n,l,r)-1)<<'\n';
    }
    return;
  }
  for(int ii=1;ii<=q;ii++){
    int l,r,k;
    cin>>l>>r>>k;
    int b[n+4];
    for(int j=l;j<=r;j++){
      b[j-l+1]=a[j];
    }
    int len=r-l+1;
    reverse(b+1,b+1+len);
    set<int>st;
    int ok=1;
    for(int i=1;i<=len;i++){
      // cout<<b[i]<<' ';
      if(st.empty()){
        st.insert(b[i]);
        continue;
      }
      if(*st.begin()>=b[i]){
        st.insert(b[i]);
        continue;
      }
      int to=*(--st.lower_bound(b[i]));
      if(to+b[i]>k){
        ok=0;
        break;
      }
      st.insert(b[i]);
    }
    cout<<ok<<'\n';
  }
}
signed main(){
  Sattar_is_the_best
  // freopen("length.in", "r", stdin);
  // freopen("length.out", "w", stdout);
  int t = 1;
  // cin >> t;
  while(noSuccess){
    tryAgain();
  }
}

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