Submission #1283007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283007		esomer	Bouquet (EGOI24_bouquet)	C++20	24 / 100	55 ms	19960 KiB

Main

#include <iostream>
#include <vector>

using namespace std;

#define int long long
#define pi pair<int,int>

const int INF = 1e9;

int log2_ceil(int n){
  return 63 - __builtin_clzll(n) + (__builtin_popcountll(n) != 1);
}

inline int L(int node){
  return 2*node;
}

inline int R(int node){
  return 2*node + 1;
}

struct segment_tree {
  int numElements, N;
  vector<int> st;

  segment_tree(int sz) : numElements(sz) {
    N = (1 << log2_ceil(numElements));

    st.assign(2*N, -INF);
    for (int i=0; i<numElements; ++i) st[i+N] = 0;
    for (int i=1; i<=N; ++i) st[i] = max(st[L(i)], st[R(i)]);;
  }

  void update(int pos, int val){
    if (pos >= numElements) return;

    pos += N;
    st[pos] = val;

    pos /= 2;
    while(pos >= 1){
      st[pos] = max(st[L(pos)], st[R(pos)]);
      pos /= 2;
    }
  }

  int query(int node, int l, int r, int a, int b){
    if (b < l || r < a) return -INF;

    if (a <= l && r <= b) {
      return st[node];
    }

    int m = (l+r)/2;
    int res=-INF;
    if (a <= m){
      res = max(res, query(L(node), l, m, a, b));
    } 
    if (b >= m+1){
      res = max(res, query(R(node), m+1, r, a, b));
    }

    return res;
  }

  int query(int a, int b){
    if (b < 0) return 0;

    return query(1, 0, N-1, a, b);
  }
};

void solve(){
  int N; cin >> N;

  vector<pi> tulips(N);
  for (pi & par : tulips) cin >> par.first >> par.second;

  vector<vector<pi> > pendUpdates(N);
  vector<int> dp(N);

  segment_tree ST(N);
  for (int i=0; i<N; ++i){
    int mx = max(0LL, ST.query(0, i-tulips[i].first-1)) + 1;
    dp[i] = mx;

    int rPos = i + tulips[i].second;
    if (rPos < N) pendUpdates[rPos].push_back(pi(i, mx));

    for (pi par : pendUpdates[i]){
      ST.update(par.first, par.second);
    }
  }

  int res = 0;
  for (int n : dp) res = max(res, n);
  cout << res << '\n';
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  solve();
  return 0;
}

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