Codeforces Round 878 (Div. 3) - C. Ski Resort (1000)

C. Ski Resort

어떤 $q$ 이상의 $a_i$ 가 없는 연속된 구간의 길이를 $L$ 이라고 한다면

$L \ge K$ 라면 이 구간에서 가능한 개수는 $\displaystyle \sum_{i=1}^{L-K+1}i=\dfrac{(L-K+1)(L-K+2)}{2}$ 이다.

이걸 정답에 모두 더해주면 된다.

void solve() {  
   int n, k, q;  
   cin >> n >> k >> q;  
   vi a(n);  
   fv(a);  
   vi idx(n);  
   idx.pb(-1);  
   for (int i = 0; i < n; i++) if (a[i] > q) idx.pb(i);  
   idx.pb(n);  
  
   int ans = 0;  
   for (int i = 1; i < sz(idx); i++) {  
      int len = idx[i] - idx[i - 1] - 1;  
      if (len >= k) {  
         ans += (len - k + 1) * (len - k + 2) / 2;  
      }  
   }  
   cout << ans << endl;  
}