Submission #173827

#	Time	Username	Problem	Language	Result	Execution time	Memory
173827		RafaelSus	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2037 ms	150704 KiB

sortbooks

#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);

int a[N],b[N];
int T[4*N],mx[4*N];

void build(int v,int tl,int tr){
  if(tl==tr){
    T[v]=b[tl];
    return;
  }
  int tm=(tl+tr)/2;
  build(v+v,tl,tm);
  build(v+v+1,tm+1,tr);
  T[v]=max(T[v+v],T[v+v+1]);
}

int l[N],r[N],mo[N],answ[N];
vector<int>idx[N];
vector<int>st[N];

int query(int v,int tl,int tr,int l,int r){
  if(l>r)return 0;
  if(tl==l&&tr==r)return T[v];
  int tm=(tl+tr)/2;
  return max(query(v+v,tl,tm,l,min(tm,r)),query(v+v+1,tm+1,tr,max(tm+1,l),r));
}

void update(int v,int tl,int tr,int pos,int val){
  if(tl==tr){
    T[v]=val;
    return;
  }
  int tm=(tl+tr)/2;
  if(pos<=tm)update(v+v,tl,tm,pos,val);
  else update(v+v+1,tm+1,tr,pos,val);
  T[v]=max(T[v+v],T[v+v+1]);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  
  int n,m;
  cin>>n>>m;
  vector<int>h;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    while(!h.empty()&&a[h.back()]<=a[i])h.pop_back();
    if(h.empty())h.pb(i);
    else{
      int idx=h.back();
      st[idx].pb(i);
      b[i]=a[idx]+a[i];
      h.pb(i);
    }
  }
  build(1,1,n);
  for(int i=1;i<=m;i++){
    cin>>l[i]>>r[i]>>mo[i];
    idx[l[i]].pb(i);
  }
  
  for(int i=1;i<=n;i++){
    for(auto x:idx[i]){
      answ[x]=query(1,1,n,i,r[x]);
    }
    for(auto x:st[i]){
      update(1,1,n,x,0);
    }
  }
  for(int i=1;i<=m;i++){
    cout<<(answ[i]<=mo[i]?"1\n":"0\n");
  }
}

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