Submission #346605

#	Time	Username	Problem	Language	Result	Execution time	Memory
346605		milleniumEeee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1873 ms	79012 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) {
  if (tl == tr) {
    tree[v] = max(tree[v], val);
    return;
  }
  int mid = (tl + tr) >> 1;
  if (pos <= mid) {
    upd(pos, val, v + v, tl, mid);
  } else {
    upd(pos, val, v + v + 1, mid + 1, tr);
  }
  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];
    scanf("%d", &a[i]);
  }
  vector <Query> vec;
  for (int i = 1; i <= q; i++) {
    int l, r, k;
    //cin >> l >> r >> k;
    scanf("%d %d %d", &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] << endl;
    printf("%d\n", ans[i]);
  }
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     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