Submission #348440

#	Time	Username	Problem	Language	Result	Execution time	Memory
348440		casperwang	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1380 ms	45164 KiB

sortbooks

#include <bits/stdc++.h>
#define tiiii tuple<int,int,int,int>
#define All(x) x.begin(), x.end()
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 1000000;
int n, m;
int w[MAXN+1];
vector <tiiii> qry;
vector <bool> ans;
stack <int> stk;

class Seg {
  private:
    int arr[MAXN*4+5];
    void pull(int now) {
      arr[now] = max(arr[now*2], arr[now*2+1]);
    }
  public:
    void mdy(int p, int k, int now=1, int l=1, int r=n) {
      if (l == p && r == p) {
        arr[now] = max(arr[now], k);
        return;
      } else if (l > p || r < p) return;
      int mid = l + r >> 1;
      mdy(p, k, now*2  , l, mid);
      mdy(p, k, now*2+1,mid+1,r);
      pull(now);
      return;
    }
    int qry(int ql, int qr, int now=1, int l=1, int r=n) {
      if (ql <= l && r <= qr) {
        return arr[now];
      } else if (l > qr || r < ql) return 0;
      int mid = l + r >> 1, mmax = 0;
      mmax = max(mmax, qry(ql, qr, now*2  , l, mid));
      mmax = max(mmax, qry(ql, qr, now*2+1,mid+1,r));
      return mmax;
    }
} seg;

void add(int id) {
  while (stk.size() && w[id] >= w[stk.top()])
    stk.pop();
  if (stk.size())
    seg.mdy(stk.top(), w[stk.top()] + w[id]);
  stk.push(id);
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> w[i];
  qry.resize(m);
  for (int i = 0; i < m; i++) {
    auto &[r, l, k, id] = qry[i];
    cin >> l >> r >> k;
    id = i;
  }
  sort(All(qry));
  ans.resize(m);
  int nowR = 0;
  for (int i = 0; i < m; i++) {
    auto &[r, l, k, id] = qry[i];
    while (nowR < r)
      add(++nowR);
    ans[id] = seg.qry(l, r) <= k;
  }
  for (int i = 0 ; i < m; i++)
    cout << ans[i] << '\n';
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void Seg::mdy(int, int, int, int, int)':
sortbooks.cpp:29:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |       int mid = l + r >> 1;
      |                 ~~^~~
sortbooks.cpp: In member function 'int Seg::qry(int, int, int, int, int)':
sortbooks.cpp:39:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |       int mid = l + r >> 1, mmax = 0;
      |                 ~~^~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:61:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     auto &[r, l, k, id] = qry[i];
      |           ^
sortbooks.cpp:69:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     auto &[r, l, k, id] = qry[i];
      |           ^

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