Submission #237458

#	Time	Username	Problem	Language	Result	Execution time	Memory
237458		ASDF123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	693 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;

const int N = (int)1e6 + 6;
int a[N];

struct T {
  int mx, best;
  vector <int> vec = {};
};
T tree[N * 4];
int n, Q;

void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v].mx = a[tl];
    tree[v].vec = {a[tl]};
    tree[v].best = 0;
    return;
  }
  int mid = tl + tr >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
  merge(tree[v + v].vec.begin(), tree[v + v].vec.end(), tree[v + v + 1].vec.begin(), tree[v + v + 1].vec.end(), back_inserter(tree[v].vec));
  tree[v].mx = max(tree[v + v].mx, tree[v + v + 1].mx);
  tree[v].best = max(tree[v + v].best, tree[v + v + 1].best);
  int another = 0;
  if (tree[v + v].mx > tree[v + v + 1].vec[0]) {
    another = tree[v + v].mx + *(--lower_bound(all(tree[v + v + 1].vec), tree[v + v].mx));
  }
  tree[v].best = max(tree[v].best, another);
}

pii get(int l, int r, int v = 1, int tl = 1, int tr = n, int Curmx = 0) { // best / maximum in l...r
  if (l > tr || tl > r) {
    return {0, 0};
  }
  if (l <= tl && tr <= r) {
    int another = 0;
    if (tree[v].vec[0] < Curmx) {
      another = Curmx + *(--lower_bound(all(tree[v].vec), Curmx));
    }
    return {max(tree[v].best, another), tree[v].mx};
  }
  int mid = tl + tr >> 1;
  int ans = 0;
  pii q1 = get(l, r, v + v, tl, mid, Curmx);
  pii q2 = get(l, r, v + v + 1, mid + 1, tr, max(Curmx, q1.sc));
  return {max(q1.fr, q2.fr), max(q1.sc, q2.sc)};
}

main() {
  cin >> n >> Q;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build(1, 1, n);

  while (Q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    if (get(l, r).fr <= k) {
      puts("1");
    } else {
      puts("0");
    }
  }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:25:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp: In function 'std::pair<int, int> get(int, int, int, int, int, int)':
sortbooks.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp:50:7: warning: unused variable 'ans' [-Wunused-variable]
   int ans = 0;
       ^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:56:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l, &r, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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