Increasing segments#11790
Autentificare

Increasing segments (Editorial)

Problem Author:

Kostiantyn Denysov

Prepared by:

Kostiantyn Denysov, Maksym Shvedchenko

Editorial by:

Kostiantyn Denysov

Let's split our array on "increasing blocks". Like if a_i < a_{i+1} then elements and i+1 are in the same block. Let's say we have of such blocks and let their sizes be: s_1, s_2, \ldots, s_k. Let's look at a specific block s_i. There are two cases:

  1. s_i < k. Then this block doesn't violate the condition from the statement.

  2. s_i \ge k. Then we need to delete at least s_i-k+1 elements from this block, so that its length becomes k-1. It is easy to see that if we don't do this, then the condition from statement will be violated. Okay, but what elements to delete? We don't want our blocks to spread (merge) somehow. They won't merge if we do not delete two elements on the borders of the block. As k \ge 3 we can always do so.

So the answer is just \sum_{i=1}^k \max(0, s_i-k+1).

Time complexity: 

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;



void test_case() {
    int n, k;
    cin >> n >> k;
    vec<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ) {
        int j = i, cnt = 1;
        while (j + 1 < n && a[j] < a[j + 1]) {
            ++cnt;
            ++j;
        }
        if (cnt >= k) {
            ans += cnt - k + 1;
        }
        i = j + 1;
    }
    cout << ans << '\n';
}



int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

     cin >> t;

    while (t--) test_case();

    return 0;
}

/*
KoRoVa!
*/
C++