CPTH/tests/MonotonousQueue/MonotonousQueue.cpp at master · ouuan/CPTH · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "../../headers/MonotonousQueue.h"

#include <algorithm>
#include <cstdio>
#include <iostream>

typedef std::pair<int, int> pii;

int main()
{
    int n, k, i;

    scanf("%d%d", &n, &k);

    std::vector<int> a(n);
    for (i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    CPTH::MonotonousQueue<pii, std::greater<pii>> mn([&](pii x) {
        return x.second > i - k;
    });

    CPTH::MonotonousQueue<pii> mx;

    assert(mx.empty());
    for (i = 1; i <= 10000; ++i)
    {
        mx.push({i * 233, i});
        assert(mx.top() == pii(i * 233, i));
    }
    mx.clear();
    assert(mx.empty());

    mx.setValidate([&](pii x) {
        return x.second > i - k;
    });

    for (i = 0; i < k - 1; ++i)
    {
        mn.push({a[i], i});
        mx.push({a[i], i});
    }

    for (i = k - 1; i < n; ++i)
    {
        mn.push({a[i], i});
        assert(!mn.empty());
        printf("%d%c", mn.top().first, " \n"[i == n - 1]);
    }

    for (i = k - 1; i < n; ++i)
    {
        mx.push({a[i], i});
        assert(!mx.empty());
        printf("%d%c", mx.top().first, " \n"[i == n - 1]);
    }

    return 0;
}