fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Fenwick {
  5.     int n;
  6.     vector<int> bit;
  7.     Fenwick(int n) : n(n), bit(n+1, 0) {}
  8.     void update(int i, int val) {
  9.         for (++i; i <= n; i += i & -i)
  10.             bit[i] = max(bit[i], val);
  11.     }
  12.     int query(int i) {
  13.         int res = 0;
  14.         for (++i; i > 0; i -= i & -i)
  15.             res = max(res, bit[i]);
  16.         return res;
  17.     }
  18. };
  19.  
  20. int main() {
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr);
  23.  
  24.     int N, D;
  25.     cin >> N >> D;
  26.     vector<long long> A(N);
  27.     for (int i = 0; i < N; i++) cin >> A[i];
  28.  
  29.     // 좌표압축
  30.     vector<long long> comp = A;
  31.     sort(comp.begin(), comp.end());
  32.     comp.erase(unique(comp.begin(), comp.end()), comp.end());
  33.     auto get = [&](long long x) {
  34.         return (int)(lower_bound(comp.begin(), comp.end(), x) - comp.begin());
  35.     };
  36.  
  37.     int M = comp.size();
  38.     Fenwick fenw(M);
  39.     deque<pair<int,int>> window; // (index, dp[index])
  40.     vector<int> dp(N, 0);
  41.  
  42.     for (int i = 0; i < N; i++) {
  43.         int ai = get(A[i]);
  44.  
  45.         // A[j] < A[i] 조건에서 dp[j] + 1 최대값
  46.         int best = fenw.query(ai - 1) + 1;
  47.  
  48.         // 그냥 이전 중에서 연결만 유지하는 경우
  49.         if (!window.empty()) {
  50.             best = max(best, window.back().second);
  51.         }
  52.  
  53.         dp[i] = best;
  54.  
  55.         // 현재 값 추가
  56.         fenw.update(ai, dp[i]);
  57.         window.emplace_back(i, dp[i]);
  58.  
  59.         // 윈도우 크기 초과하면 제거
  60.         if (i - window.front().first >= D) {
  61.             // 제거할 값이 fenw에 남아있을 수 있는데,
  62.             // 정확히 지우려면 "세그먼트트리 + multiset" 구조 필요.
  63.             // 여기선 단순화 위해 lazy 방식으로 처리 가능.
  64.             window.pop_front();
  65.         }
  66.     }
  67.  
  68.     cout << dp[N-1] << "\n";
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
7 1
100 600 600 200 300 500 500
stdout
copy 
4
https://ideone.com/xer4PS
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!