fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct SegTree {
  5.     int n;
  6.     vector<int> st;
  7.     SegTree(int n_=0): n(n_), st(4*n_+5, 0) {}
  8.     void upd(int p, int v, int node, int l, int r){
  9.         if(l==r){ st[node]=v; return; }
  10.         int m=(l+r)>>1;
  11.         if(p<=m) upd(p,v,node<<1,l,m);
  12.         else     upd(p,v,node<<1|1,m+1,r);
  13.         st[node]=max(st[node<<1], st[node<<1|1]);
  14.     }
  15.     void update(int p, int v){ if(n) upd(p,v,1,0,n-1); }
  16.     int qry(int ql, int qr, int node, int l, int r){
  17.         if(qr<l || r<ql) return 0;
  18.         if(ql<=l && r<=qr) return st[node];
  19.         int m=(l+r)>>1;
  20.         return max(qry(ql,qr,node<<1,l,m), qry(ql,qr,node<<1|1,m+1,r));
  21.     }
  22.     int query(int l, int r){ if(l>r || !n) return 0; return qry(l,r,1,0,n-1); }
  23. };
  24.  
  25. int main(){
  26.     ios::sync_with_stdio(false);
  27.     cin.tie(nullptr);
  28.  
  29.     int N, D;
  30.     cin >> N >> D;
  31.     vector<long long> A(N);
  32.     for(int i=0;i<N;i++) cin >> A[i];
  33.  
  34.     // 좌표압축
  35.     vector<long long> vals = A;
  36.     sort(vals.begin(), vals.end());
  37.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  38.     int M = (int)vals.size();
  39.     vector<int> rk(N);
  40.     for(int i=0;i<N;i++){
  41.         rk[i] = int(lower_bound(vals.begin(), vals.end(), A[i]) - vals.begin()); // 0..M-1
  42.     }
  43.  
  44.     vector<int> dp(N, 0);
  45.  
  46.     // 각 값 등급별로 "유효 구간 안에서의 dp 최대값"을 유지
  47.     vector<deque<pair<int,int>>> bucket(M);
  48.     SegTree seg(M);
  49.  
  50.     for(int i=0;i<N;i++){
  51.         // 윈도우에서 벗어나는 인덱스 제거 (i-D-1)
  52.         int out = i - D - 1;
  53.         if(out >= 0){
  54.             int r = rk[out];
  55.             if(!bucket[r].empty() && bucket[r].front().first == out){
  56.                 bucket[r].pop_front();
  57.                 seg.update(r, bucket[r].empty() ? 0 : bucket[r].front().second);
  58.             }
  59.         }
  60.  
  61.         // dp[i] = 1 + max dp[j], (j∈[i-D,i-1], A[j] < A[i])
  62.         int bestLess = (rk[i] > 0) ? seg.query(0, rk[i]-1) : 0;
  63.         dp[i] = bestLess + 1;
  64.  
  65.         // 현재 값 삽입
  66.         int r = rk[i];
  67.         auto &dq = bucket[r];
  68.         while(!dq.empty() && dq.back().second <= dp[i]) dq.pop_back();
  69.         dq.emplace_back(i, dp[i]);
  70.         seg.update(r, dq.front().second);
  71.     }
  72.  
  73.     cout << dp[N-1] << "\n"; // 반드시 마지막 날 포함
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
7 1
100 600 600 200 300 500 500
stdout 
1
https://ideone.com/FdsaAB
language:
C++ (gcc 8.3)
created:
3 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!