oj.uz

Submission #863176

# Submission time Handle Problem Language Result Execution time Memory
863176 2023-10-19T17:53:48 Z truongdoan2012 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2081 ms 153272 KB 
#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 = (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 = (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<int> 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, i, 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2081 ms 153272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 14460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -