Submission #1325260

#TimeUsernameProblemLanguageResultExecution timeMemory
1325260djsksbrbfBouquet (EGOI24_bouquet)C++20
100 / 100
138 ms15628 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> ipi;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 5;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
#define int ll

int seg[4*MAX];

void upd(int l, int r, int id, int val, int pos){
   if(l == r){
      seg[pos] = val;
      return;
   }
   
   int mid = (l + r) >> 1;
   if(id <= mid)upd(l, mid, id, val, 2*pos);
   else upd(mid + 1, r, id, val, 2*pos + 1);
   
   seg[pos]= max(seg[2*pos], seg[2*pos + 1]);
}

int que(int l, int r, int tl, int tr, int pos){
   if(r < tl || tr < l || tr < tl)return 0;
   if(tl <= l && r <= tr)return seg[pos];
   
   int mid = (l + r) >> 1;
   return max(que(l, mid, tl, tr, 2*pos), que(mid + 1, r, tl, tr, 2*pos + 1));
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   
   int n; cin >> n;
   int l[n + 5], r[n + 5];
   for(int i = 1 ; i <= n ; i++)cin >> l[i] >> r[i];
   int dp[n + 5];dp[0] = 0;
   int pref[n + 5];pref[0] = 0;
   
   priority_queue <ipi, vector<ipi>, greater<ipi>> pq;
   dp[1] = 1;
   pq.push({1 + r[1] + 1, {1, 1}});
   
   for(int i = 2 ; i <= n ; i++){
      dp[i] = 1;
      while(pq.size() && pq.top().fi <= i){
         upd(1, n, pq.top().se.fi, pq.top().se.se, 1);
         pq.pop();
      }
      
      dp[i] = que(1, n, 1, i - l[i] - 1, 1) + 1;
      pq.push({i + r[i] + 1, {i, dp[i]}});
   }
   
   int ans = 0;
   for(int i = 1 ; i <= n ; i++)ans = max(ans, dp[i]);
   cout << ans << endl;
   
   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...