Submission #346610

#	Time	Username	Problem	Language	Result	Execution time	Memory
346610		milleniumEeee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1688 ms	63972 KiB

sortbooks

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

const int MAXN = (int)1e6 + 6;

struct Query {
  int l, k, id;
  Query (int l_, int k_, int id_) {
    l = l_, k = k_, id = id_;
  }
  Query () {
    
  }
};

vector <Query> query[MAXN];
int a[MAXN];
int ans[MAXN];
int tree[MAXN * 4];

void upd(int pos, int val, int v = 1, int tl = 1, int tr = MAXN) {
  tl = 1, tr = MAXN;
  while (tl != tr) {
    int mid = (tl + tr) >> 1;
    if (pos <= mid) {
      tr = mid;
      v = v + v;
    } else {
      tl = mid + 1;
      v = v + v + 1;
    }
  }
  tree[v] = max(tree[v], val);
  v = (v >> 1);
  for (v; v >= 1; v = (v >> 1)) {
    tree[v] = max(tree[v + v], tree[v + v + 1]);
  }
}

int get(int l, int r, int v = 1, int tl = 1, int tr = MAXN) {
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  if (l > tr || tl > r) {
    return 0;
  }
  int mid = (tl + tr) >> 1;
  return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  vector <Query> vec;
  for (int i = 1; i <= q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    query[r].push_back(Query(l, k, i));
  }
  vector <pair<int, int>> st;
  for (int r = 1; r <= n; r++) {
    while (!st.empty() && st.back().first < a[r]) {
      st.pop_back();
    }
    if (!st.empty() && st.back().first > a[r]) {
      upd(st.back().second, st.back().first + a[r]);
    }
    st.push_back({a[r], r});
    while (!query[r].empty()) {
      int l = query[r].back().l;
      int k = query[r].back().k;
      int id = query[r].back().id;
      query[r].pop_back();
      ans[id] = (get(l, r) <= k);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << "\n";
  }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void upd(int, int, int, int, int)':
sortbooks.cpp:35:8: warning: statement has no effect [-Wunused-value]
   35 |   for (v; v >= 1; v = (v >> 1)) {
      |        ^

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