Submission #197407

#	Time	Username	Problem	Language	Result	Execution time	Memory
197407		IOrtroiii	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1329 ms	96100 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1 << 20;

int N, Q;
int A[MAXN];
vector<tuple<int, int, int>> qs[MAXN];
int tr[MAXN * 2];
bool ans[MAXN];

void update(int v, int val) {
   v += MAXN;
   tr[v] = max(tr[v], val);
   for (v >>= 1; v > 0; v >>= 1) {
      tr[v] = max(tr[v << 1], tr[v << 1 | 1]);
   }
}

int get(int l, int r) {
   int ans = 0;
   for (l += MAXN, r += MAXN; l <= r; l >>= 1, r >>= 1) {
      if (l & 1) ans = max(ans, tr[l++]);
      if (!(r & 1)) ans = max(ans, tr[r--]);
   }
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> N >> Q;
   for (int i = 1; i <= N; ++i) {
      cin >> A[i];
   }
   for (int i = 1; i <= Q; ++i) {
      int l, r, k;
      cin >> l >> r >> k;
      qs[l].emplace_back(r, k, i);
   }
   vector<int> st;
   for (int i = N; i > 0; --i) {
      while (!st.empty() && A[i] > A[st.back()]) {
         update(st.back(), A[i] + A[st.back()]);
         st.pop_back();
      }
      st.emplace_back(i);
      for (auto q : qs[i]) {
         ans[get<2>(q)] = get(i, get<0>(q)) <= get<1>(q);
      }
   }
   for (int i = 1; i <= Q; ++i) {
      cout << ans[i] << "\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