제출 #1131984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131984		JelalTkm	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	2292 ms	320404 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;

int mx;

struct segtree {

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

  void build(vector<int> &a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < (int) a.size()) {
        tree[x].first[0] = a[lx];
        tree[x].second.first = a[lx];
      }
    } else {
      int m = (lx + rx) >> 1;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      tree[x].first = tree[2 * x + 2].first;
      int l = lower_bound(tree[x].first.begin(), tree[x].first.end(), tree[2 * x + 1].second.first) - tree[x].first.begin();
      tree[x].second.second = max(tree[2 * x + 1].second.second, tree[2 * x + 2].second.second);
      l--;
      if (l >= 0 && tree[x].first[l] != -1)
        tree[x].second.second = max(tree[x].second.second, tree[2 * x + 1].second.first + tree[x].first[l]);
      tree[x].first.insert(tree[x].first.begin(), tree[2 * x + 1].first.begin(), tree[2 * x + 1].first.end());
      tree[x].second.first = max(tree[2 * x + 1].second.first, tree[2 * x + 2].second.first);
      sort(tree[x].first.begin(), tree[x].first.end());
    }
  }
 
  void build(vector<int> &a) {
    init((int) a.size() + 1);
    build(a, 0, 0, size);
  }

  int get(int l, int r, int x, int lx, int rx) {
    if (l >= rx || lx >= r) {
      return 0;
    }
    if (lx >= l && rx <= r) {
      int l = lower_bound(tree[x].first.begin(), tree[x].first.end(), mx) - tree[x].first.begin();
      int ans = tree[x].second.second;
      if (l >= 0 && tree[x].first[l] != -1)
        ans = max(ans, tree[x].first[l] + mx);
      mx = max(mx, tree[x].second.first);
      return ans;
    } else {
      int m = (lx + rx) >> 1;
      int s1 = get(l, r, 2 * x + 1, lx, m);
      int s2 = get(l, r, 2 * x + 2, m, rx);
      return max(s1, s2);
    }
  }

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

};

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