Submission #930208

#	Time	Username	Problem	Language	Result	Execution time	Memory
930208		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1371 ms	141828 KiB

sortbooks

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

#define ll long long
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

vector <int> g[maxn];
stack <int> st;
int a[maxn], t[4 * maxn];
int ans[maxn], res[maxn], l[maxn], r[maxn], k[maxn];

void upd(int v, int tl, int tr, int pos, int val) {
  if (tl == tr) {
    t[v] = max(val + a[pos], t[v]);
    return;
  }
  int mid = tl + tr >> 1;
  if (pos <= mid) upd(v + v, tl, mid, pos, val);
  else upd(v + v + 1, mid + 1, tr, pos, val);
  t[v] = max(t[v + v], t[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r) {
  if (l > tr || r < tl) return 0;
  if (l <= tl && tr <= r) return t[v];
  int mid = tl + tr >> 1;
  return max(get(v + v, tl, mid, l, r), get(v + v + 1, mid + 1, tr, l, r));
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    while (!st.empty() && a[st.top()] <= a[i]) {
      st.pop();
    }
    if (st.empty()) ans[i] = -1;
    else ans[i] = st.top();
    st.push(i);
  }
  for (int i = 1; i <= m; i++) {
    cin >> l[i] >> r[i] >> k[i];
    g[r[i]].pb(i);
  }
  for (int i = 1; i <= n; i++) {
    if (ans[i] != -1) upd(1, 1, n, ans[i], a[i]);
    for (auto to : g[i]) res[to] = (get(1, 1, n, l[to], r[to]) > k[to] ? 0 : 1);
  }
  for (int i = 1; i <= m; i++) {
    cout << res[i] << '\n';
  }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int mid = tl + tr >> 1;
      |             ~~~^~~~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int mid = tl + tr >> 1;
      |             ~~~^~~~

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