Submission #1131971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131971		JelalTkm	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3097 ms	58160 KiB

sortbooks

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 3e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;

struct segtree {
  
  struct node {
    int min, max, v;
  };

  vector<node> tree;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, {0, -1, 0});
  }

  int find_k(int l, int r, int k, int x, int lx, int rx) {
    if (l >= rx || lx >= r || tree[x].min >= k) {
      return -1;
    }
    if (lx >= l && rx <= r && tree[x].max < k) {
      return tree[x].max;
    } else {
      int m = (lx + rx) >> 1;
      return max(find_k(l, r, k, 2 * x + 1, lx, m), find_k(l, r, k, 2 * x + 2, m, rx));
    }
  }

  int find_k(int l, int r, int k) {
    return find_k(l, r, k, 0, 0, size);
  }

  void build(vector<int> &a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < (int) a.size()) {
        tree[x].min = tree[x].max = a[lx];
      }
    } else {
      int m = (lx + rx) >> 1;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      tree[x].min = min(tree[2 * x + 1].min, tree[2 * x + 2].min);
      tree[x].max = max(tree[2 * x + 1].max, tree[2 * x + 2].max);
      int val = find_k(m, rx, tree[2 * x + 1].max);
      if (val != -1)
        tree[x].v = tree[2 * x + 1].max + val;
      else tree[x].v = max(tree[2 * x + 1].v, tree[2 * x + 2].v);
    }
  }
 
  void build(vector<int> &a) {
    init((int) a.size() + 1);
    build(a, 0, 0, size);
  }

  pair<int, int> get(int l, int r, int x, int lx, int rx) {
    if (l >= rx || lx >= r) {
      return {0, 0};
    }
    if (lx >= l && rx <= r) {
      return {tree[x].v, tree[x].max};
    } else {
      int m = (lx + rx) >> 1;
      auto s1 = get(l, r, 2 * x + 1, lx, m);
      auto s2 = get(l, r, 2 * x + 2, m, rx);
      int val = find_k(m, min(r, rx), s1.second);
      int ans = max(s1.first, s2.first);
      if (val != -1)
        ans = max(ans, s1.second + val);
      return {ans, max(s1.second, s2.second)};
    }
  }

  int get(int l, int r) {
    auto pr = get(l, r, 0, 0, size);
    return pr.first;
  }

};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];

    segtree st;
    st.build(a);

    while (m--) {
      int l, r, k;
      cin >> l >> r >> k;
      l--;
      if (st.get(l, r) > k)
        cout << 0 << '\n';
      else cout << 1 << '\n';
    }
  }

  return 0;
}

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