Submission #1148228

#TimeUsernameProblemLanguageResultExecution timeMemory
1148228KaleemRazaSyedBouquet (EGOI24_bouquet)C++20
100 / 100
167 ms19984 KiB
#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n, ft[N];

void update(int x, int d) {
  while(x <= n) ft[x] = max(ft[x], d), x += (x & -x);
}

int get(int l)
{
  int ans = 0;
  while(l > 0) ans = max(ans, ft[l]), l -= (l & -l);
  return ans;
}

int main()
{
  int ans = 0;
  cin >> n;

  set<vector<int> > up;
  
  for(int i = 1; i <= n; i ++)
    {
      while(up.size() && up.begin()->at(0) < i)
	{
	  update(up.begin()->at(1), up.begin()->at(2));
	  up.erase(up.begin());
	}
      
      int l, r;
      cin >> l >> r;
      int sol = 1 + get(i - l - 1);
      ans = max(ans, sol);
      up.insert({i + r, i, sol});
    }
  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...