Submission #257140

#	Time	Username	Problem	Language	Result	Execution time	Memory
257140		BThero	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1393 ms	114096 KiB

sortbooks

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

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

vector<array<int, 3>> que[MAXN];
vector<int> V[MAXN];
int prv[MAXN];
int arr[MAXN];
int n, q;
int fenw[MAXN];
int ans[MAXN];

int prefMax(int p) {
  int ret = 0;
  
  for (; p > 0; --p) {
    ret = max(ret, fenw[p]);
    p &= (p + 1);
  }
  
  return ret;
}

void fenwUpd(int p, int x) {
  for (; p <= n; p |= (p + 1)) {
    fenw[p] = max(fenw[p], x);
  }
}

void solve() {
  scanf("%d %d", &n, &q);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  vector<int> vec;
  
  for (int i = 1; i <= n; ++i) {
    while (!vec.empty() && arr[vec.back()] <= arr[i]) {
      vec.pop_back();
    }
    
    prv[i] = (vec.empty() ? 0 : vec.back());
    V[prv[i]].pb(i);
    vec.pb(i);
  }
  
  for (int i = 1; i <= q; ++i) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    que[l].pb({r, k, i});
  }
  
  for (int l = n; l > 0; --l) {
    for (int idx : V[l]) {
      fenwUpd(idx, arr[idx] + arr[l]);
    }
    
    for (auto &[r, k, id] : que[l]) {
      ans[id] = (prefMax(r) <= k);
    }
  }
  
  for (int i = 1; i <= q; ++i) {
    printf("%d\n", ans[i]);
  }
}

int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     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