Submission #1148228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148228		KaleemRazaSyed	Bouquet (EGOI24_bouquet)	C++20	100 / 100	167 ms	19984 KiB

Main

#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;
}

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