| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P153PROJ - ROUND 3J - Số cặp nghịch thế |
Cho một dãy số gồm n phần tử a[1], a[2], ..., a[n] và số nguyên k. Nhiệm vụ của bạn là hãy đếm số lượng dãy con liên tiếp thỏa mãn số cặp nghịch thế trong dãy con đó >= k.
Số cặp nghịch thế của dãy con a[i], a[i+1], ..., a[j] là số cặp (u, v) thỏa mãn i <= u < v <= j và a[u] > a[v].
Input
Dòng đầu tiên là số nguyên dương n, số lượng phần tử của dãy và số nguyên k.
Dòng tiếp theo gồm n số nguyên dương, biểu diễn a[1], a[2], ..., a[n].
Giới hạn: n <= 10^5, k <= n*(n-1)/2, 0 <= a[i] <= 10^9.
Output
In ra một số nguyên duy nhất là đáp số của bài toán.
Example
Test 1:
Input:
4 1
1 2 4 0
Output:
3
Giải thích test 1:
Các dãy con a[1->4], a[2->4], a[3->4] có một cặp nghịch thế.
Test 2:
Input:
2 0
1 2
Output:
3
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-19 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
