Submission #321555

#	Time	Username	Problem	Language	Result	Execution time	Memory
321555		tushar_2658	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1989 ms	166004 KiB

sortbooks

#include "bits/stdc++.h"
using namespace std;

const int maxn = 1000005;
using ll = long long;

ll a[maxn];  

struct DATA {
  int l, r;
  ll k;
  int id;
};

DATA q[maxn];
vector<DATA> v[maxn];
vector<int> ed[maxn];

ll t[maxn << 2];

void upd(int node, int b, int e, int idx, ll val){
  if(idx > e or idx < b)return;
  if(b == idx && idx == e){
    t[node] = max(t[node], val);
    return;
  }
  int mid = (b + e) >> 1;
  if(idx <= mid)upd(2*node, b, mid, idx, val);
  else upd(2*node + 1, mid + 1, e, idx, val);
  t[node] = max(t[2*node], t[2*node + 1]);
}

ll query(int node, int b, int e, int i, int j){
  if(i > e or j < b)return 0;
  if(b >= i && j >= e)return t[node];
  int mid = (b + e) >> 1;
  return max(query(2*node, b, mid, i, j), query(2*node + 1, mid + 1, e, i, j));
}

int main(int argc, char const *argv[])
{
  int n, m;
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; ++i){
    scanf("%lld", &a[i]);
  }  
  stack<int> st;
  for(int i = n; i >= 1; --i){
    while(!st.empty() && a[st.top()] < a[i]){
      ed[st.top()].push_back(i);
      st.pop();
    }
    st.push(i);
  }
  for(int i = 1; i <= m; ++i){
    scanf("%d %d %lld", &q[i].l, &q[i].r, &q[i].k);
    q[i].id = i;
    v[q[i].r].push_back(q[i]);
  }
  vector<int> ans(m + 1);
  for(int i = 1; i <= n; ++i){
    for(auto j : ed[i]){
      upd(1, 1, n, j, a[j] + a[i]);
    }
    for(auto j : v[i]){
      ans[j.id] = query(1, 1, n, j.l, j.r) <= j.k;
    }
  }
  for(int i = 1; i <= m; ++i){
    printf("%d\n", ans[i]);
  }

  return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main(int, const char**)':
sortbooks.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%lld", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d %d %lld", &q[i].l, &q[i].r, &q[i].k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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