Submission #1268486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268486		repmann	Financial Report (JOI21_financial)	C++20	100 / 100	248 ms	17704 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int N, D, M, K;
int A[300001], I[300001];
int DP[300001];
int ST[1200001], P[1200001];
inline void Setup()
{
  K = 1;
  while(K < M) K <<= 1;
  for(int i = 1; i < (K + M); i++) {ST[i] = 0; P[i] = -1;}
  return;
}
inline void Propagate(int i)
{
  ST[i] = P[i];
  if(i < K) P[i << 1] = P[i << 1 | 1] = P[i];
  P[i] = -1;
  return;
}
inline void Set(int L, int R, int X, int i = 1, int LC = 1, int RC = K)
{
  if(P[i] != -1) Propagate(i);
  if((LC > R) || (L > RC)) return;
  if((L <= LC) && (RC <= R)) {P[i] = X; Propagate(i); return;}
  int S = (LC + RC) >> 1;
  Set(L, R, X, i << 1, LC, S);
  Set(L, R, X, i << 1 | 1, S + 1, RC);
  ST[i] = max(ST[i << 1], ST[i << 1 | 1]);
  return;
}
inline int Get(int L, int R, int i = 1, int LC = 1, int RC = K)
{
  if(P[i] != -1) Propagate(i);
  if((LC > R) || (L > RC)) return 0;
  if((L <= LC) && (RC <= R)) return ST[i];
  int S = (LC + RC) >> 1;
  return max(Get(L, R, i << 1, LC, S), Get(L, R, i << 1 | 1, S + 1, RC));
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> D;
  for(int i = 1; i <= N; i++) cin >> A[i];
  vector <pair <int, int>> scale;
  for(int i = 1; i <= N; i++) scale.push_back({A[i], i});
  sort(scale.begin(), scale.end());
  A[scale[0].second] = M = 1;
  for(int i = 1; i < N; i++)
  {
    M += scale[i].first > scale[i - 1].first;
    A[scale[i].second] = M;
  }
  Setup();
  priority_queue <pair <int, int>> H;
  for(int i = 1; i <= N; i++)
  {
//    cout << i << ":\n";
    while(H.size() && (H.top().second < (i - D))) H.pop();
//    if(H.size()) cout << -H.top().first << '\n';
    if(H.size()) Set(1, -H.top().first - 1, 0);
    DP[i] = Get(1, A[i] - 1) + 1;
//    cout << DP[i] << '\n';
    Set(A[i], A[i], max(Get(A[i], A[i]), DP[i]));
    H.push({-A[i], i});
  }
  cout << Get(1, M) << '\n';

  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35