Submission #168297

#	Time	Username	Problem	Language	Result	Execution time	Memory
168297		Nordway	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1414 ms	107392 KiB

sortbooks

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=1e6+11;
const int M=1e6+11;
const int inf=1e9;
const ll INF=1e18;
const ll mod=1e9+7;
const double EPS=1e-9;

int t[4*N];
vector<int>inv[N];
pair<pair<int,int>,pair<int,int>>q[N];
int ans[N];
int a[N];

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

int get(int v,int tl,int tr,int l,int r){
  if(tl>r||l>tr)return 0;
  if(l<=tl&&tr<=r)return t[v];
  int tm=(tl+tr)/2;
  return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}

int main(){
  ios_base::sync_with_stdio(NULL);
  cin.tie(nullptr),cout.tie(nullptr);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  stack<int>st;
  for(int i=n;i>=1;i--){
    while(!st.empty()&&a[st.top()]<a[i]){
      inv[i].pb(st.top());
      st.pop();
    }
    st.push(i);
  }
  for(int i=1;i<=m;i++){
    cin>>q[i].x.x>>q[i].x.y>>q[i].y.x;
    q[i].y.y=i;
  }
  sort(q+1,q+m+1);
  reverse(q+1,q+m+1);
  int l=n;
  for(int i=1;i<=m;i++){
    while(q[i].x.x<=l){
      for(int j=0;j<sz(inv[l]);j++){
        upd(1,1,n,inv[l][j],a[inv[l][j]]+a[l]);
      }
      l--;
    }
    ans[q[i].y.y]=(get(1,1,n,1,q[i].x.y)<=q[i].y.x);
  }
  for(int i=1;i<=m;i++){
    cout<<ans[i]<<nl;
  }
}

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