Submission #1328915

#TimeUsernameProblemLanguageResultExecution timeMemory
1328915avighnaBouquet (EGOI24_bouquet)C++20
100 / 100
46 ms5716 KiB
#include <bits/stdc++.h>

using namespace std;

class fenwick_tree {
  int n;
  vector<int> bit;

public:
  fenwick_tree(int n) : n(n), bit(n + 1) {}

  int query(int i) {
    int ans = 0;
    for (i += 1; i > 0; i -= i & -i) {
      ans = max(ans, bit[i]);
    }
    return ans;
  }

  void apply(int i, int x) {
    for (i += 1; i <= n; i += i & -i) {
      bit[i] = max(bit[i], x);
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> l(n), r(n);
  for (int i = 0; i < n; ++i) {
    cin >> l[i] >> r[i];
  }

  vector<int> dp(n, 1);
  fenwick_tree tree(n);
  priority_queue<pair<int, int>> pq;
  pq.push({-(r[0] + 0), 0});
  for (int i = 1; i < n; ++i) {
    while (!pq.empty() && -pq.top().first <= i - 1) {
      int i = pq.top().second;
      tree.apply(i, dp[i]);
      pq.pop();
    }
    if (i - l[i] - 1 >= 0) {
      int q = tree.query(i - l[i] - 1);
      dp[i] = max(dp[i], tree.query(i - l[i] - 1) + 1);
    }
    pq.push({-(r[i] + i), i});
  }

  cout << *max_element(dp.begin(), dp.end()) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...