Submission #863192

#	Time	Username	Problem	Language	Result	Execution time	Memory
863192		truongdoan2012	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1703 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
 
using i64 = long long;
const int N = 1e6 + 10;
i64 f[N << 1];
 
void upd(int id, int l, int r, int p, i64 v) {
  if (l == r) {
    return void(f[id] = v);
  }
  int mid = (l + r) >> 1;
  int rc = id + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(id + 1, l, mid, p, v);
  } else {
    upd(rc, mid + 1, r, p, v);
  }
  f[id] = max(f[id << 1], f[id << 1 | 1]);
}
 
//max from [0, x]
i64 get(int id, int l, int r, int u, int v) {
  if (l > v || r < u) {
    return -1e18;
  }
  if (l >= u && r <= v) {
    return f[id];
  }
  int mid = (l + r) >> 1;
  int rc = id + ((mid - l + 1) << 1);
  return max(get(id + 1, l, mid, u, v), get(rc, mid + 1, r, u, v));
}
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector<i64> a(n), ans(m, 1);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  map<int, vector<array<i64, 3>>> mp;
  stack<int> st;
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    mp[--v].push_back({--u, c, i});
  }
  for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] <= a[i]) {
      st.pop();
    }
    //a[pv] > a[i]
    if (!st.empty())
      upd(0, 0, n - 1, st.top(), a[st.top()] + a[i]);
    for (auto [l, w, id] : mp[i]) {
      ans[id] = get(0, 0, n - 1, l, i) <= w;
    }
    st.push(i);
  }
  for (int i = 0; i < m; i++) {
    cout << ans[i] << '\n';
  }
}
 
int main() {
  cin.tie(nullptr) -> sync_with_stdio(false);
  int TC = 1;
  //cin >> TC;
  while (TC--) {
    solve();
  }
}

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