Submission #1171237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171237		orzdraiduwu	Bouquet (EGOI24_bouquet)	C++20	100 / 100	225 ms	37992 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int MXQ = (1 << 30) - 1;
const int INF = 1e11;
using pr = array<int, 2>;
struct Node {
  Node *l = nullptr, *r = nullptr;
  int v = 0;
};
 
void push(Node *u) { if(u == nullptr) u = new Node; }
int query(Node *u, int lq, int rq, int l, int r) {
  if(l > rq or r < lq) return 0;
  if(l >= lq and r <= rq) return u->v;
  int m = (l+r)/2;
  int ans = -INF;
  if(u->l != nullptr) ans = max(ans, query(u->l, lq, rq, l, m));
  if(u->r != nullptr) ans = max(ans, query(u->r, lq, rq, m+1, r));
  return ans;
}
 
void update(Node *u, int i, int x, int l, int r) {
  if(l == r) {
    u->v = x;
    return;
  }
 
  int m = (l+r)/2;
  if(i <= m) {
    if(u->l == nullptr) u->l = new Node;
    update(u->l, i, x, l, m);
  }
  
  else {
    if(u->r == nullptr) u->r = new Node;
    update(u->r, i, x, m+1, r);
  }
  
  u->v = max((u->l?u->l->v:-INF), (u->r?u->r->v:-INF));
}

void solve() {
  int n; cin >> n;
  vector<pr> v(n);
  for(int i = 0 ; i < n ; i++) {
    cin >> v[i][0] >> v[i][1];
    // cout << v[i][0] << " " << v[i][1] << endl;
  }

  // sort(v.begin(), v.end(), [](pr a, pr b) {return a[1] < b[1];});
  Node *root = new Node;
  // queue<pr> upd;
  vector<vector<int>> upd(3*n);
  int dp[n]; fill(&dp[0], &dp[0] + n, 1);
  for(int i = 0 ; i < n ; i++) {
    // while(!upd.empty() and upd.front()[0] == i) {
    while(i > 0 and upd[i-1].size()) {
      // cout << i << " " << upd.front()[0] << " " << upd.front()[1] << endl;
      update(root, upd[i-1].back(), dp[upd[i-1].back()], 0, MXQ);
      // upd.pop();
      upd[i-1].pop_back();
    }
    
    dp[i] = max(1LL, query(root, 0, i-v[i][0]-1, 0, MXQ) + 1);
    // upd.push({v[i][1], i});
    upd[i+v[i][1]].push_back(i);
  }

  // for(int i = 0 ; i < n ; i++) cout << dp[i] << " ";
  cout << *max_element(&dp[0], &dp[0] + n) << endl;
}

signed main() {
  // int t; cin >> t;
  int t = 1;
  while(t--) solve();
}

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