fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.   JOI mart – Impression Score
  6.   O(N log N) 풀이
  7.   아이디어 요약:
  8.   - 인덱스 x를 A[x] 오름차순(같은 값은 x 내림차순)으로 처리.
  9.   - processed = 이미 처리한 인덱스들의 집합 (경계용으로 0, n+1 포함)
  10.   - barrier = "왼쪽 경계 후보" 집합. 초기엔 [1..n-D]를 모두 담고 시작.
  11.     어떤 인덱스 x를 처리할 때, x의 processed 이웃 (prel, prer)을 보고
  12.     prer - prel > D라면, x를 경계로 좌/우 D안에 있는 구간의 barrier를 지운다.
  13.     그 뒤 x의 왼쪽 경계 left = (barrier.lower_bound(x)의 직전 원소) 또는 1.
  14.   - dp[x] = 1 + max(dp[left..x-1])  (세그트리로 range max)
  15.   - 정답 = max(dp[1..n])  (마지막 날 포함 조건은 중간 삽입으로 항상 충족 가능)
  16. */
  17.  
  18. struct SegTree {
  19.     int n;
  20.     vector<int> st;
  21.     SegTree(int N=0): n(N), st(4*N+5, 0) {}
  22.     void update(int node, int l, int r, int pos, int val){
  23.         if(l==r){ st[node]=val; return; }
  24.         int m=(l+r)>>1;
  25.         if(pos<=m) update(node<<1, l, m, pos, val);
  26.         else       update(node<<1|1, m+1, r, pos, val);
  27.         st[node] = max(st[node<<1], st[node<<1|1]);
  28.     }
  29.     void update(int pos, int val){ update(1,1,n,pos,val); }
  30.     int query(int node, int l, int r, int ql, int qr){
  31.         if(qr<l || r<ql) return 0;
  32.         if(ql<=l && r<=qr) return st[node];
  33.         int m=(l+r)>>1;
  34.         return max(query(node<<1,l,m,ql,qr), query(node<<1|1,m+1,r,ql,qr));
  35.     }
  36.     int query(int l, int r){ if(l>r) return 0; return query(1,1,n,l,r); }
  37. };
  38.  
  39. int main(){
  40.     ios::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.  
  43.     int n, D;
  44.     cin >> n >> D;
  45.     vector<long long> A(n+1);
  46.     for(int i=1;i<=n;i++) cin >> A[i];
  47.  
  48.     // 값 기준 정렬: (값 오름차순, 인덱스 내림차순)
  49.     vector<int> perm(n);
  50.     iota(perm.begin(), perm.end(), 1);
  51.     sort(perm.begin(), perm.end(), [&](int x, int y){
  52.         if (A[x] != A[y]) return A[x] < A[y];
  53.         return x > y;
  54.     });
  55.  
  56.     SegTree st(n);
  57.     vector<int> dp(n+1, 0);
  58.  
  59.     // processed: 이미 처리된 인덱스(경계 포함)
  60.     set<int> processed;
  61.     processed.insert(0);
  62.     processed.insert(n+1);
  63.  
  64.     // barrier: 왼쪽 경계 후보들
  65.     set<int> barrier;
  66.     for(int i=1;i<=n-D;i++) barrier.insert(i);
  67.  
  68.     for(int x : perm){
  69.         // processed 이웃 찾기
  70.         auto it = processed.lower_bound(x);
  71.         int prer = *it;
  72.         int prel = *prev(it);
  73.  
  74.         // 큰 공백을 x가 메울 때, x와 양쪽 경계 사이가 D 이내면 해당 구간의 barrier 제거
  75.         if (prer - prel > D) {
  76.             if (prer - x <= D) {
  77.                 // 지울 구간: [x .. prer-1]이지만, barrier엔 최대 n-D까지만 존재
  78.                 int L = x, R = min(prer-1, n-D);
  79.                 if (L <= R) {
  80.                     auto itL = barrier.lower_bound(L);
  81.                     while (itL != barrier.end() && *itL <= R) itL = barrier.erase(itL);
  82.                 }
  83.             }
  84.             if (x - prel <= D) {
  85.                 int L = max(prel, 1), R = min(x, n-D);
  86.                 if (L <= R) {
  87.                     auto itL = barrier.lower_bound(L);
  88.                     while (itL != barrier.end() && *itL <= R) itL = barrier.erase(itL);
  89.                 }
  90.             }
  91.         }
  92.  
  93.         processed.insert(x);
  94.  
  95.         // x에 대한 왼쪽 경계 left 구하기
  96.         auto itb = barrier.lower_bound(x);
  97.         int left = (itb == barrier.begin() ? 1 : *prev(itb));
  98.  
  99.         // dp[x] = 1 + max(dp[left..x-1])
  100.         dp[x] = st.query(left, x-1) + 1;
  101.         st.update(x, dp[x]);
  102.     }
  103.  
  104.     // 전체 최댓값 = 정답 (마지막 날 포함 조건은 중간 삽입으로 항상 만족시키며 점수는 감소하지 않음)
  105.     cout << st.query(1, n) << '\n';
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 5256KB
comments (?)
stdin 
7 1
100 600 600 200 300 500 500
stdout 
3
https://ideone.com/0WIrOJ
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!