Submission #922637

#	Time	Username	Problem	Language	Result	Execution time	Memory
922637		myst6	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1383 ms	92872 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

// need to get highest number which is in the wrong place
// and the lowest number

// [1]
// [1, 8]
// [1, 4, 8]
// [1, 2, 4, 8]
// once a number is out of place, it is like that for any addition
// so can add events for numbers being out of place
// it becomes out of place on the next smaller number to the right

// [3, 5, 1, 8, 2]
// [0, 0, 0, 0, 0] l=4
// [0, 0, 0, 0, 8] l=3
// [0, 0, 0, 0, 8] l=2
// [0, 0, 5, 0, 8] l=1
// [0, 0, 5, 0, 8] l=0

// so trivialis maximis?

const int inf = 1 << 30;

template <typename Info>
struct Tree { 
  vector<Info> info;
  Tree(int size) { info.resize(size*4); }
  void update(int v, int x, int xl, int xr, Info delta) {
    if (xl == xr) {
      info[x] = delta;
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) update(v, x*2, xl, xm, delta);
      else update(v, x*2+1, xm+1, xr, delta);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  Info query(int l, int r, int x, int xl, int xr) {
    if (l > r) return Info();
    if (l == xl && r == xr) {
      return info[x]; 
    } else {
      int xm = (xl + xr) / 2;
      Info left = query(l, min(r, xm), x*2, xl, xm);
      Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
      return left.combine(right);
    }
  }
};

struct MinInfo {
  int m;
  MinInfo(int M) : m(M) {}
  MinInfo() : m(1<<30) {}
  MinInfo combine(MinInfo &other) { return {min(m, other.m)}; }
};

struct MaxInfo {
  int m;
  MaxInfo(int M) : m(M) {}
  MaxInfo() : m(0) {}
  MaxInfo combine(MaxInfo &other) { return {max(m, other.m)}; }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  vector<int> w(N);
  for (int i=0; i<N; i++) cin >> w[i];
  vector<int> next(N, -1);
  stack<int> S;
  for (int i=0; i<N; i++) {
    while (S.size() && w[S.top()] > w[i]) {
      next[S.top()] = i;
      S.pop();
    }
    S.push(i);
  }
  vector<array<int,4>> queries(M);
  for (int i=0; i<M; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    queries[i] = {{l-1, r-1, k, i}};
  }
  Tree<MinInfo> minTree(N);
  Tree<MaxInfo> maxTree(N);
  vector<int> ans(M);
  int line = N;
  for (int i=0; i<M; i++) {
    int l = queries[i][0], r = queries[i][1];
    int k = queries[i][2], q = queries[i][3];
    while (line > l) {
      line--;
      minTree.update(line, 1, 0, N-1, w[line]);
      if (next[line] != -1) {
        maxTree.update(next[line], 1, 0, N-1, w[line]);
      }
    }
    int lo = minTree.query(l, r, 1, 0, N-1).m;
    int hi = maxTree.query(l, r, 1, 0, N-1).m;
    if (hi == 0 || lo + hi <= k) ans[q] = 1;
  }
  for (int x : ans) cout << x << "\n";
  return 0;
}

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