Submission #1188059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188059		akamizane	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	624 ms	92924 KiB

sortbooks

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

#define debug(...) 42

#define int long long
using ll = long long;

struct BIT{
   vector<int> bit;
   BIT(int n){bit = vector<int>(n + 1);}
   void up(int k, int x){
      k++;
      for(; k; k -= k & -k){
         bit[k] = max(bit[k], x);
      }
   }
   int get(int k){
      k++;
      int ans = 0;
      for (;k < bit.size(); k += k & -k){
         ans = max(ans, bit[k]);
      }
      return ans;
   }
};

void solve(){
   int n, q;
   cin >> n >> q;
   vector<int> a(n + 1);
   a[0] = 1e9 + 5;
   for (int i = 1; i <= n; i++) cin >> a[i];
   vector<int> to[n + 1];
   vector<array<int, 3>> que;
   for (int i = 0; i < q; i++){
      int l, r, k;
      cin >> l >> r >> k;
      que.push_back({l, r, k});
      to[r].push_back(i);
   }
   BIT bit(1e6);
   vector<int> ans(q);
   vector<int> st = {0};
   for (int i = 1; i <= n; i++){
      while(a[st.back()] <= a[i]) st.pop_back();
      bit.up(st.back(), a[i] + a[st.back()]);
      st.push_back(i);
      for (auto idx : to[i]){
         auto [l, r, k] = que[idx];
         ans[idx] = bit.get(l) <= k;
      }
   }
   for (auto x : ans) cout << x << "\n";
}

int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int tt = 1;
   // cin >> tt;
   while(tt--) {
      solve();
   }
   return 0;
}

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