제출 #1337241

#제출 시각아이디문제언어결과실행 시간메모리
1337241rafsanamin2020Bouquet (EGOI24_bouquet)C++20
24 / 100
72 ms16876 KiB
#include <bits/stdc++.h>
#define l first
#define r second

using namespace std;

class SegmentTree
{
public:
  int N;
  vector<int> tree;

  SegmentTree(int n)
  {
    N = n;
    tree = vector<int>(4 * N, 1);
  }

  int combine(int x, int y)
  {
    return max(x, y);
  }

  void insert(int i, int v, int idx = 0, int l = 0, int r = -1)
  {
    if (r == -1)
      r = N - 1;

    if (l == r && r == i)
    {
      tree[idx] = combine(tree[idx], v);
      return;
    }

    if (l <= i && r >= i)
    {

      tree[idx] = combine(tree[idx], v);

      int mid = (l + r) / 2;
      insert(i, v, 2 * idx + 1, l, mid);
      insert(i, v, 2 * idx + 2, mid + 1, r);
    }
  }

  int query(int w, int l = 0, int r = -1, int idx = 0)
  {

    if (r == -1)
      r = N - 1;

    // cout << l << " " << r << " \n";

    if (w < l)
    {
      return 0;
    }

    if (l == r || r <= w)
      return tree[idx];

    int mid = (l + r) / 2;

    return combine(query(w, l, mid, 2 * idx + 1), query(w, mid + 1, r, 2 * idx + 2));
  }
};

int solve4()
{
  int K;
  vector<pair<int, int>> Q;
  cin >> K;
  vector<int> dp(K, 1);
  vector<vector<pair<int, int>>> queue(K);
  for (int i = 0; i < K; i++)
  {
    int L, R;
    cin >> L >> R;
    Q.push_back({L, R});
  }

  SegmentTree ST(K + 1);

  for (int i = 1; i < K; i++)
  {

    for (pair<int, int> q : queue[i])
    {
      ST.insert(q.second, q.first);
    }

    dp[i] = max(ST.query(i - Q[i].l - 1) + 1, dp[i]);

    int nxt = i + Q[i].r + 1;

    if (nxt < K)
      queue[nxt].push_back({dp[i], i});
  }

  // for (int x : dp)
  // {
  //   cout << x << " ";
  // }
  // cout << "\n";

  return *max_element(dp.begin(), dp.end());
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cout << solve4();
}
#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...