Submission #237461

#	Time	Username	Problem	Language	Result	Execution time	Memory
237461		ASDF123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	77 / 100	1107 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
#define pb push_back
using namespace std;

const int N = (int)1e6 + 6;
const int INF = (int)2e9 + 9;
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)};
}

void subtask3(vector <pair<pii, int>> query) {
  bool ok = 1;
  int mn = INF;
  for (int i = 1; i <= n; i++) {
    mn = min(mn, a[i]);
  }

  for (auto c : query) {
    ok &= (c.sc < mn);
  }
  if (ok) {
    vector <int> pref(n + 5, 0);
    a[n + 1] = 2e9 + 9;
    for (int i = 1; i <= n; i++) {
      pref[i] = pref[i - 1];
      if (a[i] > a[i + 1]) {
        pref[i]++;
      }
    }
    for (auto c : query) {
      int l = c.fr.fr, r = c.fr.sc, k = c.sc;
      if (l == r) {
        puts("1");
      } else {
        if (pref[r - 1] - pref[l - 1]) {
          puts("0");
        } else {
          puts("1");
        }
      }
    }
    exit(0);
  } else {
    return;
  }
}

main() {
  cin >> n >> Q;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  vector <pair<pii, int>> query;
  while (Q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    query.pb({{l, r}, k});
  }
  subtask3(query);

  build(1, 1, n);
  for (auto c : query) {
    if (get(c.fr.fr, c.fr.sc).fr <= c.sc) {
      puts("1");
    } else {
      puts("0");
    }
  }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:28: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:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
sortbooks.cpp:53:7: warning: unused variable 'ans' [-Wunused-variable]
   int ans = 0;
       ^~~
sortbooks.cpp: In function 'void subtask3(std::vector<std::pair<std::pair<int, int>, int> >)':
sortbooks.cpp:79:37: warning: unused variable 'k' [-Wunused-variable]
       int l = c.fr.fr, r = c.fr.sc, k = c.sc;
                                     ^
sortbooks.cpp: At global scope:
sortbooks.cpp:96:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:104: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: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23