Submission #869596

# Submission time Handle Problem Language Result Execution time Memory
869596 2023-11-05T01:57:14 Z NeroZein Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
3000 ms 22144 KB
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 1e6 + 6;

int ans[N]; 
int seg[N * 2];

void upd(int nd, int l, int r, int p, int v) {
  if (l == r) {
    seg[nd] = v;
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v);
  }
  seg[nd] = max(seg[nd + 1], seg[rs]); 
}

int qry(int nd, int l, int r, int s, int e) {
  if (l >= s && r <= e) {
    return seg[nd]; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e); 
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e);
    } else {
      return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  vector<int> a(n); 
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  stack<int> stk;
  vector<array<int, 4>> ranges; 
  //for (int i = 0; i < q; ++i) {
    //int l, r, v;
    //cin >> l >> r >> v; 
    //--l, --r; 
    //ranges.push_back({l, r, -v, i});
  //}
  for (int i = n - 1; i >= 0; --i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      ranges.push_back({i, stk.top(), -(a[i] + a[stk.top()]), -1});//ranges with higher value come before
      stk.pop();
    }
    stk.push(i); 
  }
  //deb(ranges) cout << '\n';
  for (int i = 0; i < q; ++i) {
    int ql, qr, qv;
    cin >> ql >> qr >> qv; 
    --ql, --qr;
    int res = 1; 
    for (auto [l, r, v, _] : ranges) {
      v = -v;
      if (ql <= l && qr >= r && qv < v) {
        res = 0; 
      }
    }
    cout << res << '\n'; 
  }
  //sort(ranges.begin(), ranges.end()); 
  //for (auto [l, r, v, i] : ranges) {
    //v = -v;
    //if (i == -1) {
      //upd(0, 0, n - 1, r, v); 
    //} else {
      //int mx = qry(0, 0, n - 1, l, r);
      //ans[i] = (mx <= v); 
    //}
  //}
  //for (int i = 0; i < q; ++i) {
    //cout << ans[i] << '\n'; 
  //}
  return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 6 ms 476 KB Output is correct
12 Correct 12 ms 604 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 27 ms 860 KB Output is correct
15 Correct 23 ms 604 KB Output is correct
16 Correct 11 ms 600 KB Output is correct
17 Correct 6 ms 604 KB Output is correct
18 Correct 16 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 22144 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 3032 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 6 ms 476 KB Output is correct
12 Correct 12 ms 604 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 27 ms 860 KB Output is correct
15 Correct 23 ms 604 KB Output is correct
16 Correct 11 ms 600 KB Output is correct
17 Correct 6 ms 604 KB Output is correct
18 Correct 16 ms 604 KB Output is correct
19 Execution timed out 3045 ms 7760 KB Time limit exceeded
20 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 6 ms 476 KB Output is correct
12 Correct 12 ms 604 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 27 ms 860 KB Output is correct
15 Correct 23 ms 604 KB Output is correct
16 Correct 11 ms 600 KB Output is correct
17 Correct 6 ms 604 KB Output is correct
18 Correct 16 ms 604 KB Output is correct
19 Execution timed out 3052 ms 22144 KB Time limit exceeded
20 Halted 0 ms 0 KB -