Submission #598982

#	Time	Username	Problem	Language	Result	Execution time	Memory
598982		Plurm	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	100 / 100	2657 ms	66496 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

int w[1000005];
int ans[1000005];

int rt[4000005];
int lb[4000005];
int rb[4000005];

void build(int c, int l, int r) {
  lb[c] = l;
  rb[c] = r;
  rt[c] = 1e9;
  int k = (l + r) / 2;
  if (l != r) {
    build(2 * c, l, k);
    build(2 * c + 1, k + 1, r);
  }
}

void update(int c, int l, int r, int x) {
  if (lb[c] == l && rb[c] == r) {
    rt[c] = min(rt[c], x);
    return;
  }
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r) {
    update(2 * c, l, k, x);
    update(2 * c + 1, k + 1, r, x);
  } else if (r <= k) {
    update(2 * c, l, r, x);
  } else {
    update(2 * c + 1, l, r, x);
  }
}

int query(int c, int i, int mx = 1e9) {
  mx = min(mx, rt[c]);
  if (lb[c] == rb[c])
    return mx;
  int k = (lb[c] + rb[c]) / 2;
  if (i <= k)
    return query(2 * c, i, mx);
  else
    return query(2 * c + 1, i, mx);
}

void maintain(int i, int j) {
  // add (i, j) to some range data structure...
  update(1, 1, i, j);
}

bool check(int i, int j) {
  // check whether there exists a pair (i', j') such that i <= i' < j' <= j in
  // the data structure
  return query(1, i) <= j;
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  stack<int> stk;
  vector<pair<int, int>> interesting;
  for (int i = 1; i <= n; i++) {
    scanf("%d", w + i);
    while (!stk.empty() && w[stk.top()] <= w[i])
      stk.pop();
    if (!stk.empty())
      interesting.push_back({stk.top(), i});
    stk.push(i);
  }
  while (!stk.empty())
    stk.pop();
  for (int i = n; i > 0; i--) {
    while (!stk.empty() && w[stk.top()] >= w[i])
      stk.pop();
    if (!stk.empty())
      interesting.push_back({i, stk.top()});
    stk.push(i);
  }
  sort(interesting.begin(), interesting.end(),
       [](pair<int, int> x, pair<int, int> y) {
         return w[x.first] + w[x.second] > w[y.first] + w[y.second];
       });
  vector<tuple<int, int, int, int>> queries;
  for (int i = 0; i < m; i++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    queries.emplace_back(l, r, k, i);
  }
  sort(queries.begin(), queries.end(),
       [](tuple<int, int, int, int> x, tuple<int, int, int, int> y) {
         return get<2>(x) > get<2>(y);
       });
  build(1, 1, n);
  int lptr = 0;
  for (auto q : queries) {
    int l, r, k, i;
    tie(l, r, k, i) = q;
    while (lptr < interesting.size() &&
           w[interesting[lptr].first] + w[interesting[lptr].second] > k) {
      maintain(interesting[lptr].first, interesting[lptr].second);
      lptr++;
    }
    ans[i] = check(l, r) ? 0 : 1;
  }
  for (int i = 0; i < m; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:101:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     while (lptr < interesting.size() &&
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d", w + i);
      |     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     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: 23 / 23