Submission #521726

#	Time	Username	Problem	Language	Result	Execution time	Memory
521726		inluminas	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1350 ms	100536 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;

struct id{
  int l=0,k=0,idx=0;
};

vector<id>adj[lmt];

int a[lmt],lft[lmt],tree[3*lmt],ans[lmt];

void update(int at,int L,int R,int pos,int val){
  if(L==R){
    tree[at]=val;
    return;
  }
  int mid=(L+R)>>1;
  if(pos<=mid) update(at*2,L,mid,pos,val);
  else update(at*2+1,mid+1,R,pos,val);
  tree[at]=max(tree[at*2],tree[at*2+1]);
}

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){
    return tree[at];
  }
  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;
  vector<array<int,4>>q;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  stack<int>s;
  for(int i=1;i<=n;i++){
    lft[i]=i;
    while(!s.empty() && a[s.top()]<=a[i]){
      lft[i]=lft[s.top()];
      s.pop();
    }
    s.push(i);
  }
  for(int i=1;i<=m;i++){
    int l,r,k;
    cin>>l>>r>>k;
    adj[r].push_back({l,k,i});
  }
  for(int i=1;i<=n;i++){
    if(lft[i]-1>0) update(1,1,n,lft[i]-1,a[i]+a[lft[i]-1]);
    for(auto x:adj[i]){
      ans[x.idx]=(x.k>=query(1,1,n,x.l,i));
    }
  }

  for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
  return 0;
}

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