Submission #1221352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221352		lorenzo-frittoli	Bouquet (EGOI24_bouquet)	C++20	100 / 100	104 ms	7224 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <array>

using namespace std;
using ai3 = array<int,3>;

struct SegTree {
  int base, ql, qr;
  vector<int> tree;

  SegTree(int N) {
    base = 1;
    while (base < N) base *= 2;
    tree.resize(2*base, 0);
  }

  void upd(int i, int x) {
    i += base;
    tree[i] = max(x, tree[i]);
    i /= 2;
    for (; i > 0; i /= 2) tree[i] = max(tree[2*i], tree[2*i+1]);
  }

  int __mx(int i, int l, int r) {
    if (qr <= l || r <= ql) return 0;
    if (ql <= l && r <= qr) return tree[i];
    int m = (l+r) / 2;
    return max(__mx(2*i, l, m), __mx(2*i+1, m, r));
  }

  int mx(int l, int r) {
    if (r <= l) return 0;
    ql = l; qr = r;
    return __mx(1, 0, base);
  }
};

int main() {
  int N; cin >> N;
  vector<int> L(N), R(N);
  for (int i = 0; i < N; i++) cin >> L[i] >> R[i];
  
  SegTree st(N);
  priority_queue<ai3, vector<ai3>, greater<ai3>> pq;
  for (int i = 0; i < N; i++) {
    int score = st.mx(0, i-L[i]) + 1;
    pq.push({i+R[i], i, score});
    while (pq.size() && pq.top()[0] <= i) {
      auto[_,pos,val] = pq.top();
      pq.pop();
      st.upd(pos, val);
    }
  }
  
  int out = st.mx(0,N);
  while (pq.size()) {
    auto[_,pos,val] = pq.top();
    pq.pop();
    out = max(out, val);
  }

  cout << out << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30