Submission #237450

#	Time	Username	Problem	Language	Result	Execution time	Memory
237450		ASDF123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	8 / 100	3109 ms	232144 KiB

sortbooks

/*
  no pain, no gain
*/

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define pii pair<int, int>
#define all(s) s.begin(), s.end()
#define prev myrza4321
#define y1 myrza1234
#define OK puts("OK")
using namespace std;

const int N = (int)1e6 + 6;
const int INF = (int)2e9 + 9;

int a[N];
int n, Q;
vector <int> tree[N * 4];

int get(int l, int r, int big, int v = 1, int tl = 1, int tr = n) {
  if (l <= tl && tr <= r) {
    if (tree[v][0] < big) {
      int pos = lower_bound(all(tree[v]), big) - tree[v].begin() - 1;
      return tree[v][pos];
    } else {
      return 0;
    }
  }
  if (l > tr || tl > r) {
    return 0;
  }
  int mid = tl + tr >> 1;
  return max(get(l, r, big, v + v, tl, mid), get(l, r, big, v + v + 1, mid + 1, tr));
}

void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v].pb(a[tl]);
    return;
  }
  int mid = tl + tr >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
  merge(tree[v + v].begin(), tree[v + v].end(), tree[v + v + 1].begin(), tree[v + v + 1].end(), back_inserter(tree[v]));
}

int calc(int tl, int tr, int k) {
  if (tl == tr) {
    return 0;
  }

  int mid = tl + tr >> 1;
  int res = 0;
  int mxl = get(tl, mid, INF);
  int mxr = get(mid + 1, tr, mxl);

  if (mxl && mxr) {
    res = max(res, mxl + mxr);
  }
  res = max(res, calc(tl, mid, k));
  res = max(res, calc(mid + 1, tr, k));
  return res;
}

void solve() {
  int l, r, k;
  scanf("%d %d %d", &l, &r, &k);
  bool ok = (calc(l, r, k) <= k);
  if (ok) {
    puts("1");
  } else {
    puts("0");
  }
}

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

Compilation message (stderr)

sortbooks.cpp: In function 'int get(int, int, int, int, int, int)':
sortbooks.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp: In function 'int calc(int, int, int)':
sortbooks.cpp:59:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp: At global scope:
sortbooks.cpp:83:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &l, &r, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~

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