Submission #330461

#	Time	Username	Problem	Language	Result	Execution time	Memory
330461		AlexLuchianov	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	3074 ms	210424 KiB

sortbooks

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000000;
int const inf = 1000000000;

class SegmentTree{
private:
  std::vector<std::vector<int>> aint;
  std::vector<int> answer;
public:
  SegmentTree(int n) {
    answer.resize(1 + 4 * n);
    aint.resize(1 + 4 * n);
  }
  int extract(int node, int from, int to, int target) {
    if(target <= aint[node][0])
      return 0;
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2) 
      if(x + jump < aint[node].size() && aint[node][x + jump] < target)
        x += jump;
    return target + aint[node][x];
  }

  void build(int node, int from, int to, std::vector<int> aux) {
    if(from < to) {
      int mid = (from + to) / 2;
      build(node * 2, from, mid, aux);
      build(node * 2  + 1, mid + 1, to, aux);
      aint[node].resize(to - from + 1);
      std::merge(aint[node * 2].begin(), aint[node * 2].end(),
                 aint[node * 2 + 1].begin(), aint[node * 2 + 1].end(),
                 aint[node].begin()); 
      answer[node] = std::max(answer[node * 2], answer[node * 2 + 1]);
      answer[node] = std::max(answer[node], extract(node * 2 + 1, mid + 1, to, aint[node * 2].back()));
    } else {
      answer[node] = 0;
      aint[node].push_back(aux[from]);
    }
  }
  

  int query(int node, int from, int to, int x, int y, int &smax) {
    if(from == x && to == y) {
      int result = std::max(answer[node], extract(node, from, to, smax));
      smax = std::max(smax, aint[node].back());
      return result;
    } else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y, smax);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y, smax);
      else {
        int result1 = query(node * 2, from, mid, x, mid, smax);
        int result2 = query(node * 2 + 1, mid + 1, to, mid + 1, y, smax);
        return std::max(result1, result2);
      }
    }
  }
};

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, q;
  std::cin >> n >> q;
  std::vector<int> aux(1 + n);
  for(int i = 1;i <= n; i++)
    std::cin >> aux[i];
  SegmentTree aint(n);
  aint.build(1, 1, n, aux);
  for(int i = 1; i <= q; i++)  {
    int x, y, k;
    std::cin >> x >> y >> k;
    int smax = 0;
    std::cout << (aint.query(1, 1, n, x, y, smax) <= k) << '\n';
  }
  return 0;
}

Compilation message (stderr)

sortbooks.cpp: In member function 'int SegmentTree::extract(int, int, int, int)':
sortbooks.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |       if(x + jump < aint[node].size() && aint[node][x + jump] < target)
      |          ~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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