oj.uz

Submission #898122

# Submission time Handle Problem Language Result Execution time Memory
898122 2024-01-04T10:38:56 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 50 ms 96416 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define tp3 tuple<int, int, int>

const int N = 1e6+6, inf = INT_MAX;

int n, m, mnA, mxA, mxK, a[N];
vector<int> pos[N];
vector<tp3> q[N];
bitset<N> ans;

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  mnA = inf;
  mxA = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    mnA = min(mnA, a[i]);
    mxA = max(mxA, a[i]);
    pos[a[i]].push_back(i);
  }

  mxK = 0;
  for (int i = 0; i < m; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    l--; r--;
    mxK = max(mxK, k);
    q[l].push_back(make_tuple(r, k, i));
  }

  if (max(n, m) <= 5000) {
    for (int l = 0; l < n; l++) {
      sort(all(q[l]));

      int r = l;
      int mx = a[l];
      int mxSum = 0;
      for (auto& [nwR, k, idx] : q[l]) {
        while (r < nwR) {
          r++;
          mx = max(mx, a[r]);
          mxSum = max(mxSum, (mx > a[r] ? mx+a[r] : 0));
        }
        ans[idx] = (mxSum <= k);
      }
    }
  }

  if (mxK < mnA) {
    vector<int> b;
    b.push_back(0);
    for (int i = 1; i < n; i++) {
      if (a[i] < a[i-1]) {
        b.push_back(i);
      }
    }

    for (int l = 0; l < n; l++) {
      sort(all(q[l]));

      for (auto& [r, k, idx] : q[l]) {
        int x = upper_bound(all(b), l) - b.begin();
        int y = upper_bound(all(b), l) - b.begin();
        ans[idx] = (x == y);
      }
    }
  }

/*
  if (mxA <= 1000) {
    for (int l = 0; l < n; l++) {
      sort(all(q[l]));

      for (auto& [r, k, idx] : q[l]) {
        int x = upper_bound(all(b), l) - b.begin();
        int y = upper_bound(all(b), l) - b.begin();
        ans[idx] = (x == y);
      }
    }
  }
  */

  for (int i = 0; i < m; i++) {
    cout << ans[i] << "\n";
  }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47708 KB Output is correct
2 Correct 10 ms 47544 KB Output is correct
3 Runtime error 45 ms 96416 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47708 KB Output is correct
2 Correct 10 ms 47544 KB Output is correct
3 Runtime error 45 ms 96416 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 96336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47708 KB Output is correct
2 Correct 10 ms 47544 KB Output is correct
3 Runtime error 45 ms 96416 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47708 KB Output is correct
2 Correct 10 ms 47544 KB Output is correct
3 Runtime error 45 ms 96416 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -