Submission #898123

#	Time	Username	Problem	Language	Result	Execution time	Memory
898123		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	695 ms	64124 KiB

sortbooks

#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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23