Submission #1284103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284103		lmquan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1658 ms	141128 KiB

sortbooks

#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kN = 1e6 + 1;

struct T {
  long long x, y, z;
};

long long n, m, w[kN], result[kN];
vector<T> q[kN];

struct SegmentTree {
  struct Node {
    long long _max, s;
    Node() {
      _max = s = 0;
    }
  };

  int n;
  vector<Node> st;

  SegmentTree(int _n) : n(_n) {
    st.resize(4 * n + 1);
  }

  void Lazy(int i) {
    st[2 * i]._max += st[i].s;
    st[2 * i].s += st[i].s;
    st[2 * i + 1]._max += st[i].s;
    st[2 * i + 1].s += st[i].s;
    st[i].s = 0;
  }

  void Upd(int i, int l, int r, int u, int v, long long x) {
    if (l > v || r < u) {
      return ;
    }
    if (u <= l && r <= v) {
      st[i]._max += x;
      st[i].s += x;
      return ;
    }
    Lazy(i);
    int mid = (l + r) / 2;
    Upd(2 * i, l, mid, u, v, x);
    Upd(2 * i + 1, mid + 1, r, u, v, x);
    st[i]._max = max(st[2 * i]._max, st[2 * i + 1]._max);
  }

  void Update(int beg, int end, long long v) {
    Upd(1, 1, n, beg, end, v);
  }

  long long Q(int i, int l, int r, int u, int v) {
    if (l > v || r < u) {
      return 0;
    }
    if (u <= l && r <= v) {
      return st[i]._max;
    }
    Lazy(i);
    int mid = (l + r) / 2;
    return max(Q(2 * i, l, mid, u, v), Q(2 * i + 1, mid + 1, r, u, v));
  }

  long long Query(int beg, int end) {
    return Q(1, 1, n, beg, end);
  }
};

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
  }
  for (int i = 1; i <= m; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    q[l].push_back({r, k, i});
  }

  SegmentTree tree(n);
  for (int i = 1; i <= n; i++) {
    tree.Update(i, i, w[i]);
  }
  stack<int> st;
  for (int i = n; i >= 1; i--) {
    while (!st.empty() && w[i] > w[st.top()]) {
      int a = st.top();
      st.pop();
      tree.Update(a, a, w[a]);
      tree.Update(a + 1, (!st.empty() ? st.top() - 1 : n), -w[a]);
    }
    tree.Update(i, i, -w[i]);
    tree.Update(i + 1, (!st.empty() ? st.top() - 1 : n), w[i]);
    st.push(i);
    for (auto [x, y, z] : q[i]) {
      result[z] = (tree.Query(i, x) <= y);
    }
  }

  for (int i = 1; i <= m; i++) {
    cout << result[i] << '\n';
  }

  return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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