Submission #651231

#	Time	Username	Problem	Language	Result	Execution time	Memory
651231		weakweakweak	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	30 / 100	1018 ms	14556 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

const int MXN=1010000;
int n, m, o[MXN];

struct seg1{
  int a[MXN*4];
  int f(int i, int j){return min(i, j);}
  void build(int l, int r, int id){
    if(l==r){a[id]=o[l]; return;}
    int mid=(l+r)/2;
    build(l, mid, id*2); build(mid+1, r, id*2+1);
    a[id]=f(a[id*2], a[id*2+1]);}
  int query(int l, int r, int ql, int qr ,int id){
    if(ql<=l&&r<=qr)return a[id];
    int res=INT_MAX, mid=(l+r)/2;
    if(ql<=mid)res=f(res, query(l, mid, ql, qr, id*2));
    if(qr>mid)res=f(res, query(mid+1, r, ql, qr, id*2+1));
    return res;}
}s1;

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin>>n>>m;
  for(int i=1; i<=n; i++)cin>>o[i];
  if(n<=5000&&m<=5000){
    while(m--){
      int l, r, k;
      cin>>l>>r>>k;
      int mx=o[l], chk=1;
      for(int i=l; i<=r; i++){
        if(o[i]<mx&&mx+o[i]>k)chk=0;
        mx=max(mx, o[i]);}
      cout<<chk<<'\n';
    }  
  }
  else{
    for(int i=1; i<=n; i++)o[i]=o[i+1]-o[i];
    s1.build(1, n-1, 1);
    while(m--){
      int l, r, k;
      cin>>l>>r>>k;
      if(l==r){cout<<1<<'\n'; continue;}
      int x=s1.query(1, n-1, l, r-1, 1);
      if(x<0)cout<<0<<'\n';
      else cout<<1<<'\n';}
  }
return 0;}

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