Submission #1184420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184420		zhamshid	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3094 ms	74704 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 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]=a[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]);
  }
  build(1,1,n);
  for(int i=1;i<=q;i++){
    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];
    }
    sort(b+1,b+1+(r-l+1));
    map<int,int>mp;
    for(int j=1;j<=(r-l+1);j++){
      mp[b[j]]=j+l-1;
    }
    int ok=1;
    for(int j=l;j<=r;j++){
      int L=j+1,R=mp[b[j]];
      // cout<<L<<' '<<R<<'\n';
      if(L>R) continue;
      // cout<<ok<<'\n';
      for(int t=L;t<=R;t++){
        if(a[t]+a[j]>k){
          ok=0;
          break;
        }
      }
      if(ok==0) break;
    }
    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: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23