Submission #1076067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076067		Flandre	Bouquet (EGOI24_bouquet)	C++17	24 / 100	107 ms	25692 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

// loal is the cutest girl

#define ll long long
#define ld long double
#define pow2(x) (x)*(x)
#define le left
#define ri right
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pll pair<long long, long long>
#define isvowel(x) (x) == 'a' || (x) == 'i' || (x) == 'u' || (x) == 'e' || (x) == 'o'
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

const ld EPS = 1e-9;
const ld PI = 3.141592653589793238462643383279502884197169399375105820974944;

const int maxn = 2e5+5;
int n;
pii a[maxn];

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  
  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> a[i].fi >> a[i].se;
  }

  int dp[n][2];
  vector<int> ls[n];
  set<int> active;
  dp[0][0] = 0;
  dp[0][1] = 1;
  if (a[0].se > 0) {if (a[0].se < n) ls[a[0].se].pb(0);}
  else active.insert(0);

  for (int i = 1; i < n; i++) {
    dp[i][0] = max(dp[i-1][1], dp[i-1][0]);

    // find rightmost possible
    auto it = active.lower_bound(i-a[i].fi);
    if (it == active.begin()) dp[i][1] = 1;
    else {
      it--;
      dp[i][1] = 1+max(dp[*it][1], dp[*it][0]);
    }

    if (i+a[i].se < n)
      ls[i+a[i].se].pb(i);
    for (auto j : ls[i]) active.insert(j);
  }

  cout << max(dp[n-1][1], dp[n-1][0]);
  
  return 0;
}

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