제출 #1151201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151201		rxlfd314	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1296 ms	116376 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct ST {
  const int N;
  vt<int> ans, st_const, lset;
  ST(const int n) : N(n), ans(n<<2), st_const(n<<2), lset(n<<2, -1) {}
  #define lc i << 1
  #define rc lc | 1
  void build(const vt<int> &A, const int i, const int tl, const int tr) {
    if (tl == tr)
      st_const[i] = A[tl];
    else {
      const int tm = tl + tr >> 1;
      build(A, lc, tl, tm);
      build(A, rc, tm+1, tr);
      st_const[i] = max(st_const[lc], st_const[rc]);
    }
  }
  void build(const vt<int> &A) {
    build(A, 1, 0, N-1);
  }
  void push(const int i) {
    if (lset[i] < 0)
      return;
    lset[lc] = lset[rc] = lset[i];
    ans[lc] = st_const[lc] + lset[i];
    ans[rc] = st_const[rc] + lset[i];
    lset[i] = -1;
  }
  void rset(const int ql, const int qr, const int v, const int i, const int tl, const int tr) {
    if (tl > qr || tr < ql)
      return;
    if (ql <= tl && tr <= qr)
      ans[i] = st_const[i] + v, lset[i] = v;
    else {
      push(i);
      const int tm = tl + tr >> 1;
      rset(ql, qr, v, lc, tl, tm);
      rset(ql, qr, v, rc, tm+1, tr);
      ans[i] = max(ans[lc], ans[rc]);
    }
  }
  void rset(const int ql, const int qr, const int v) {
    rset(ql, qr, v, 1, 0, N-1);
  }
  int query(const int ql, const int qr, const int i, const int tl, const int tr) {
    if (tl > qr || tr < ql)
      return 0;
    if (ql <= tl && tr <= qr)
      return ans[i];
    push(i);
    const int tm = tl + tr >> 1;
    return max(query(ql, qr, lc, tl, tm), query(ql, qr, rc, tm+1, tr));
  }
  int query(const int ql, const int qr) {
    return query(ql, qr, 1, 0, N-1);
  }
  #undef lc
  #undef rc
};

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N, M;
  cin >> N >> M;
  vt<int> A(N);
  for (auto &i : A)
    cin >> i;
  vt<int> L(M), R(M), K(M);
  vt<vt<int>> sweep(N);
  FOR(i, 0, M-1) {
    cin >> L[i] >> R[i] >> K[i], L[i]--, R[i]--;
    sweep[L[i]].push_back(i);
  }
  
  ST st(N);
  st.build(A);
  vt<int> stk, ans(M);
  ROF(i, N-1, 0) {
    while (size(stk) && A[i] > A[stk.back()])
      stk.pop_back();
    const int j = size(stk) ? stk.back() : N;
    st.rset(i+1, j-1, A[i]);
    stk.push_back(i);
    for (const auto &q : sweep[i])
      ans[q] = st.query(L[q], R[q]) <= K[q];
  }
  
  for (const auto &i : ans)
    cout << 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