Submission #213772

#	Time	Username	Problem	Language	Result	Execution time	Memory
213772		quocnguyen1012	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2258 ms	154232 KiB

sortbooks

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

class segment_tree
{
#define lc id << 1
#define rc id << 1 | 1
private:
  vector<int> ST; int n;
  void update(int id, int l, int r, int pos, int val)
  {
    if(l > pos || r < pos) return;
    if(l == r){
      ST[id] = max(ST[id], val);
      return;
    }
    int mid = (l + r) / 2;
    update(lc, l, mid, pos, val); update(rc, mid + 1, r, pos, val);
    ST[id] = max(ST[lc], ST[rc]);
  }
  int get(int id, int l, int r, int L, int R)
  {
    if(R < l || r < L) return -2e9;
    if(L <= l && r <= R) return ST[id];
    int mid = (l + r) / 2;
    return max(get(lc, l, mid, L, R), get(rc, mid + 1, r, L, R));
  }
public:
  void init(int _n)
  {
    n = _n;
    ST.assign(4 * n + 5, 0);
  }
  void update(int p, int v)
  {
    update(1, 1, n, p, v);
  }
  int get(int l, int r)
  {
    return get(1, 1, n, l, r);
  }
#undef lc
#undef rc
}tr;

const int maxn = 1e6 + 5;

int N, Q, a[maxn], l[maxn], r[maxn], k[maxn], res[maxn];
vector<int> query[maxn], add[maxn];
vector<int> st;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> Q;
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
    while(st.size() && a[st.back()] <= a[i]) st.pop_back();
    if(st.size()) add[st.back()].pb(i);
    st.pb(i);
  }
  for(int i = 1; i <= Q; ++i){
    cin >> l[i] >> r[i] >> k[i];
    query[l[i]].eb(i);
  }
  tr.init(N);
  for(int i = N; i >= 1; --i){
    for(int j : add[i]) tr.update(j, a[i] + a[j]);
    for(int id : query[i]){
      res[id] = (tr.get(l[id], r[id]) <= k[id]);
    }
  }
  for(int i = 1; i <= Q; ++i)
    cout << res[i] << '\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