Submission #1030045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030045		AdamGS	Financial Report (JOI21_financial)	C++17	100 / 100	2060 ms	48612 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7;
int T[LIM], dp[LIM], jaki[LIM], tr[4*LIM], lazy[4*LIM], N=1;
set<int>S;
vector<int>V[LIM];
pair<int,int>P[LIM];
void spl(int v) {
  tr[2*v]+=lazy[v];
  tr[2*v+1]+=lazy[v];
  lazy[2*v]+=lazy[v];
  lazy[2*v+1]+=lazy[v];
  lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
  if(r<a || b<l) return;
  if(a<=l && r<=b) {
    tr[v]+=x;
    lazy[v]+=x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=max(tr[2*v], tr[2*v+1]);
}
void upd2(int v, int x) {
  v+=N;
  tr[v]=x;
  v/=2;
  while(v) {
    tr[v]=max(tr[2*v], tr[2*v+1]);
    v/=2;
  }
}
int cnt2(int l, int r) {
  if(l>r) return 0;
  l+=N; r+=N;
  int ans=max(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, tr[l+1]);
    if(r%2==1) ans=max(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
int cnt(int v, int l, int r, int a, int b) {
  if(r<a || b<l) return 0;
  if(a<=l && r<=b) return tr[v];
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  return max(cnt(2*v, l, mid, a, b), cnt(2*v+1, mid+1, r, a, b));
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, d;
  cin >> n >> d;
  while(N<n) N*=2;
  rep(i, n) tr[N+i]=i+1;
  for(int i=N-1; i; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
  rep(i, n) cin >> T[i];
  rep(i, n) P[i]={T[i], -i};
  sort(P, P+n);
  rep(i, n) {
    int x=-P[i].nd;
    int a=cnt(1, 0, N-1, x, x);
    auto it=S.lower_bound(x);
    int b=n-1;
    if(it!=S.end()) b=*it;
    S.insert(x);
    upd(1, 0, N-1, x, b, -a);
    int po=x, ko=n-1;
    while(po<ko) {
      int sr=(po+ko)/2;
      if(cnt(1, 0, N-1, x, sr)<d) po=sr+1; else ko=sr;
    }
    V[po].pb(x);
    jaki[x]=i;
  }
  rep(i, 2*N) tr[i]=0;
  rep(i, n) {
    dp[i]=cnt2(0, jaki[i])+1;
    upd2(jaki[i], dp[i]);
    for(auto j : V[i]) upd2(jaki[j], 0);
  }
  int ans=0;
  rep(i, n) ans=max(ans, dp[i]);
  cout << ans << '\n';
}

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