제출 #618026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618026		Abrar_Al_Samit	Financial Report (JOI21_financial)	C++17	100 / 100	501 ms	25248 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MX = 3e5 + 5;

int st[MX*4];
int n, D;
int a[MX];


void upd(int l, int r, int id, int val, int v) {
  if(l==r) {
    st[v] = val;
    return;
  }
  int mid = (l+r)/2;
  if(id<=mid) upd(l, mid, id, val, v*2);
  else upd(mid+1, r, id, val, v*2+1);

  st[v] = max(st[v*2], st[v*2+1]);
}
int query(int l, int r, int L, int R, int v) {
  if(l>=L && r<=R) {
    return st[v];
  }
  if(l>R || r<L) return 0;

  int mid = (l+r)/2;
  return max(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+1));
}
void PlayGround() {
  cin>>n>>D;
  for(int i=1; i<=n; ++i) {
    cin>>a[i];
  }

  multiset<int>ms;
  set<pair<int,int>>bounds;
  int rht[n+1];
  fill(rht, rht+n+1, n);
  for(int i=n; i>n-D; --i) {
    ms.insert(a[i]);
  }


  for(int i=n-D+1; i>0; --i) {
    int nb = *ms.begin();
    int to = i+D-1;

    bounds.insert({nb, to});

    auto it = bounds.lower_bound(make_pair(nb, to));
    while(it!=bounds.begin()) {
      auto p = prev(it);
      if(p->second>it->second) {
        bounds.erase(p);
      } else if(p->second==it->second) {
        bounds.erase(it);
        break;
      } else break;
    }

    if(i>1) {
      auto it = bounds.upper_bound(make_pair(a[i-1]+1, -1));
      if(it==bounds.end()) {
        rht[i-1] = n;
      } else {
        rht[i-1] = it->second;
      }

      ms.erase(ms.find(a[i+D-1]));
      ms.insert(a[i-1]);
    }
  }


  int Order[n+1];
  iota(Order, Order+n+1, 0);
  sort(Order+1, Order+n+1, [&] (int i, int j) {
    if(a[i]!=a[j]) return a[i]>a[j];
    return i<j;
  });

  int ans = 0;
  for(int i=1; i<=n; ++i) {
    int cur = query(1, n, Order[i], rht[Order[i]], 1) + 1;
    upd(1, n, Order[i], cur, 1);

    ans = max(ans, cur);
  }

  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  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