Submission #854139

#	Time	Username	Problem	Language	Result	Execution time	Memory
854139		NeroZein	Financial Report (JOI21_financial)	C++17	100 / 100	175 ms	11772 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

struct segtree {
  int n;
  vector<int> seg;
  segtree(int n_) : n(n_) {
    seg.resize(2 * n - 1); 
  }
  void upd(int nd, int l, int r, int p, int v) {
    if (l == r) {
      seg[nd] = v;
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (p <= mid) {
      upd(nd + 1, l, mid, p, v);
    } else {
      upd(rs, mid + 1, r, p, v); 
    }
    seg[nd] = max(seg[nd + 1], seg[rs]);
  }
  void upd(int p, int v) {
    upd(0, 0, n - 1, p, v); 
  }
  int qry(int nd, int l, int r, int s, int e) {
    if (l >= s && r <= e) {
      return seg[nd]; 
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e); 
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e);
      } else {
        return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
      }
    }
  }
  int qry(int s, int e) {
    return qry(0, 0, n - 1, s, e); 
  }
  int dive(int nd, int l, int r, int s, int e, int key) {
    if (l > e || r < s || key >= seg[nd]) {
      return n - 1;
    }
    if (l == r) {
      return l; 
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    int ret = dive(nd + 1, l, mid, s, e, key);
    if (ret == n - 1) {
      ret = dive(rs, mid + 1, r, s, e, key);       
    }
    return ret; 
  }
  int dive(int s, int e, int key) {
    return dive(0, 0, n - 1, s, e, key); 
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, d;
  cin >> n >> d;
  vector<pair<int,int>> a(n); 
  for (int i = 0; i < n; ++i) {
    cin >> a[i].first; 
    a[i].second = i; 
  }
  segtree m(n);
  deque<int> dq;
  for (int i = 0; i < n; ++i) {
    while (!dq.empty() && dq.back() > a[i].first) {
      dq.pop_back();
    }
    dq.push_back(a[i].first);
    if (i >= d - 1) {
      m.upd(i, dq.front()); 
      if (dq.front() == a[i - d + 1].first) {
        dq.pop_front(); 
      }
    } else {
      m.upd(i, -1); 
    }
  }
  vector<int> r(n, n - 1); 
  for (int i = 0; i < n - d; ++i) {
    r[a[i].second] = m.dive(i + d , n - 1, a[i].first); 
  }
  sort(a.begin(), a.end(), [](pair<int,int> i, pair<int,int> j) {
    return i.first != j.first ? i.first > j.first : i.second < j.second;
  });
  segtree dp(n); 
  for (int i = 0; i < n; ++i) {
    auto [v, ind] = a[i];
    int rightmost = r[ind];
    dp.upd(ind, dp.qry(ind, rightmost) + 1); 
  }
  cout << dp.seg[0] << '\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