Submission #362373

#	Time	Username	Problem	Language	Result	Execution time	Memory
362373		vkgainz	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1255 ms	97768 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
const int MX = 1e6 + 5;
#define f first
#define s second
int seg[2 * MX];
int n, m;
void upd(int i, int v) {
  i+=n;
  seg[i] = max(seg[i], v);
  while(i>1) {
    i/=2;
    seg[i] = max(seg[2*i], seg[2*i+1]);
  }
}
int query(int l, int r) {
  l+=n, r+=n;
  int ans = 0;
  while(l<r) {
    if(l%2) ans = max(ans, seg[l++]);
    if(r%2) ans = max(ans, seg[--r]);
    l/=2, r/=2;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  vector<int> w(n);
  for(int i=0;i<n;i++) cin >> w[i];
  vector<pair<pair<int, int>, int>> queries[n];
  for(int i=0;i<m;i++) {
    int l, r, k; cin >> l >> r >> k;
    --l, --r;
    queries[l].push_back({{r, k}, i});
  }
  vector<int> in;
  vector<int> ans(m);
  for(int i=n-1;i>=0;i--) {
    while(in.size() && w[i] > w[in.back()]) {
      upd(in.back(), w[i] + w[in.back()]);
      in.pop_back();
    }
    in.push_back(i);
    for(auto &it : queries[i]) {
      ans[it.s] = query(i, it.f.f+1) <= it.f.s;
    }
  }
  for(auto &it : ans) cout << it << "\n";
}

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