Submission #1346555

#TimeUsernameProblemLanguageResultExecution timeMemory
1346555julia_08Bouquet (EGOI24_bouquet)C++20
100 / 100
141 ms52268 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;

struct node{
  int max, lc, rc;
};

int l[MAXN], r[MAXN];

int root[MAXN], dp[MAXN];

vector<node> seg;

int create(){
  seg.push_back({0, 0, 0});
  return (int) seg.size() - 1;
}

int update(int x, int lx, int rx, int i, int val){

  int nx = create();

  seg[nx] = seg[x];

  if(lx == rx){
    seg[nx].max = max(seg[nx].max, val);
    return nx;
  }

  int m = (lx + rx) >> 1;

  if(i <= m){

    int aux = update(seg[nx].lc, lx, m, i, val);
    seg[nx].lc = aux;

  } else{

    int aux = update(seg[nx].rc, m + 1, rx, i, val);
    seg[nx].rc = aux;

  }

  seg[nx].max = max(seg[seg[nx].lc].max, seg[seg[nx].rc].max);
  return nx;

}

int query(int x, int lx, int rx, int l, int r){

  if(rx < l || lx > r) return 0;

  if(l <= lx && rx <= r) return seg[x].max;

  int m = (lx + rx) >> 1;
  return max(query(seg[x].lc, lx, m, l, r), query(seg[x].rc, m + 1, rx, l, r));

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  for(int i=1; i<=n; i++) cin >> l[i] >> r[i];

  dp[0] = 0;

  int sz = (n + 1);

  create();

  int cur = create();

  root[0] = cur;

  int ans = 0;

  for(int i=1; i<=n; i++){

    int j = max(0, i - l[i] - 1);

    // dp[i] := ultimo que peguei foi o i
    
    dp[i] = 1 + query(root[j], 1, sz, 1, i - 1);
    ans = max(ans, dp[i]);

    cur = update(cur, 1, sz, i + r[i], dp[i]);
    root[i] = cur;

  }

  cout << ans << "\n";

  return 0;
}
#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...