fork download
copy 
  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.     if(!(cin >> N >> D)) return 0;
  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.     // 각 값등급별로 창 내 dp의 최대를 유지하는 deque (index 증가, dp 내림차순)
  45.     vector<deque<pair<int,int>>> bucket(M);
  46.     SegTree seg(M);
  47.  
  48.     vector<int> dp(N, 0);
  49.     int ans = 0;
  50.  
  51.     for(int i=0;i<N;i++){
  52.         // 창에서 빠져나가는 인덱스 (i-D-1) 제거
  53.         int out = i - D - 1;
  54.         if(out >= 0){
  55.             int r = rk[out];
  56.             if(!bucket[r].empty() && bucket[r].front().first == out){
  57.                 bucket[r].pop_front();
  58.                 seg.update(r, bucket[r].empty() ? 0 : bucket[r].front().second);
  59.             }
  60.             // 만약 out가 deque에서 이미 뒷부분에서 제거되어 없었다면, 할 일 없음
  61.         }
  62.  
  63.         // dp[i] 계산: 창 [i-D, i-1]에서 값 < A[i]인 것들 중 dp 최댓값 + 1
  64.         int bestLess = (rk[i] > 0) ? seg.query(0, rk[i]-1) : 0;
  65.         dp[i] = bestLess + 1;
  66.  
  67.         // 현재 값등급의 deque에 (i, dp[i]) 삽입: dp 내림차순 유지
  68.         int r = rk[i];
  69.         auto &dq = bucket[r];
  70.         while(!dq.empty() && dq.back().second <= dp[i]) dq.pop_back();
  71.         dq.emplace_back(i, dp[i]);
  72.         seg.update(r, dq.front().second);
  73.  
  74.         ans = max(ans, dp[i]);
  75.     }
  76.  
  77.     cout << ans << '\n';
  78.     return 0;
  79. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 6
100 500 200 400 600 300
stdout
copy 
4
https://ideone.com/5xztgZ
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!