CSES - Datatähti 2020 loppu - Results
Submission details
Task:Riippuliito
Sender:Antti Paraoanu
Submission time:2020-02-09 16:11:54 +0200
Language:C++17
Status:READY
Result:18
Feedback
groupverdictscore
#1ACCEPTED18
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s2, 3details
#9ACCEPTED0.01 s2, 3details
#10ACCEPTED0.01 s2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13--2, 3details
#14ACCEPTED0.01 s2, 3details
#15ACCEPTED0.03 s3details
#16ACCEPTED0.16 s3details
#17ACCEPTED0.16 s3details
#18ACCEPTED0.11 s3details
#19ACCEPTED0.15 s3details
#20--3details
#21--3details
#22ACCEPTED0.01 s1, 2, 3details
#23ACCEPTED0.01 s1, 2, 3details
#24ACCEPTED0.01 s1, 2, 3details
#25ACCEPTED0.01 s1, 2, 3details
#26ACCEPTED0.01 s1, 2, 3details
#27ACCEPTED0.01 s1, 2, 3details
#28ACCEPTED0.01 s1, 2, 3details
#29ACCEPTED0.01 s1, 2, 3details

Compiler report

input/code.cpp: In function 'int ans(std::vector<long unsigned int>&, int, int, int, maxtree*)':
input/code.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < m.size() - 1; ++i) {
                     ~~^~~~~~~~~~~~~~
input/code.cpp:162:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < m.size() - 1; ++i) {
                     ~~^~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <cstdint>

struct maxtree {
    uint64_t m;
    int indx;
    int mxcount;
    int from;
    int to;
    struct maxtree* a;
    struct maxtree* b;
};

struct maxtree* mkMaxtree(std::vector<uint64_t>& vec, int from, int to) {
    //std::cout << "Called mkMaxtree with from=" << from << " to=" << to << "\n";
    struct maxtree* r = new maxtree;
    if (to - from >= 2) {
        r->a = mkMaxtree(vec, from, (from + to)/2);
        r->b = mkMaxtree(vec, (from + to)/2, to);
        /*
        if (r->a->m < r->b->m) {
            auto tmp = r->b;
            r->b = r->a;
            r->a = tmp;
        }
        */
        if (r->a->m == r->b->m) {
            r->indx = -1;
            r->mxcount = r->a->mxcount + r->b->mxcount;
            r->m = r->a->m;
        } else if (r->a->m > r->b->m) {
            r->indx = r->a->indx;
            r->mxcount = r->a->mxcount;
            r->m = r->a->m;
        } else {
            r->indx = r->b->indx;
            r->mxcount = r->b->mxcount;
            r->m = r->b->m;
        }
    } else {
        r->indx = from;
        r->m = vec[from];
        r->mxcount = 1;
    }
    r->from = from;
    r->to = to;
    //std::cout << "Returning with r-> from=" << r->from << " to=" << r->to << " indx=" << r->indx << " mxcount=" << r->mxcount << "m=" << r->m << "\n";
    return r;
}

struct maxtree* submaxtree(struct maxtree* t, int from, int to) {
    if (t->to - t->from < 2)
        return t;
    if (to <= (t->from + t->to)/2) {
        return submaxtree(t->a, from, to);
    } else if (from >= (t->from + t->to)/2) {
        return submaxtree(t->b, from, to);
    } else {
        return t;
    }
}


uint64_t getMax(struct maxtree* t, int from, int to) {
    //std::cout << "Called getMax with from=" << from << " to=" << to << "\n";
    if (from >= to)
        return 0;
    if (from >= t->to || to <= t->from)
        return 0;
    t = submaxtree(t, from, to);
    if (t->mxcount == 1 && t->indx >= from && t->indx < to) {
        return t->m;
    } else {
        auto a = getMax(t->a, from, to);
        auto b = getMax(t->b, from, to);
        return std::max(a, b);
    }
}

void getMaxes(struct maxtree* t, int from, int to, std::vector<int>& v, uint64_t m) {
    //std::cout << "Called getMaxes with from=" << from << " to=" << to << " m=" << m << "\n";
    if (from >= to)
        return;
    t = submaxtree(t, from, to);
    if (t->m < m)
        return;
    if (t->mxcount == 1 && t->indx >= from && t->indx < to) {
        v.push_back(t->indx);
    } else {
        if (t->a->m >= m)
            getMaxes(t->a, from, t->a->to, v, m);
        if (t->b->m >= m)
            getMaxes(t->b, t->b->from, to, v, m);
    }
}

int ans(std::vector<uint64_t>& vec, int a, int b, int from, struct maxtree* t) {
    //std::cout << "Called ans with a=" << a << " b=" << b << " from=" << from << "\n";
    t = submaxtree(t, a, b);
    std::vector<int> m;
    m.reserve(10);
    uint64_t mx = 0;
    int ret = 0;

    m.push_back(a - 1);
    /*
    for (int i = a; i < from; ++i) {
        if (vec[i] > mx) {
            m.clear();
            m.push_back(a - 1);
            mx = vec[i];
        }
        if (vec[i] >= mx) {
            m.push_back(i);
        }
    }
    */
    mx = getMax(t, a, from);
    //std::cout << "mx: " << mx << "\n";
    getMaxes(t, a, from, m, mx);
    m.push_back(from);
    /*
    std::cout << "m (a): [";
    for (auto i : m) {
        std::cout << i << ", ";
    }
    std::cout << "]\n";
    */
    for (int i = 1; i < m.size() - 1; ++i) {
        int a = ans(vec, m[i - 1] + 1, m[i + 1], m[i], t);
        if (a > ret) {
            ret = a;
        }
    }
    mx = 0;
    m.clear();
    m.push_back(from);
    /*
    for (int i = from  + 1; i < b; ++i) {
        if (vec[i] > mx) {
            m.clear();
            m.push_back(from);
            mx = vec[i];
        }
        if (vec[i] >= mx) {
            m.push_back(i);
        }
    }
    */
    mx = getMax(t, from + 1, b);
    //std::cout << "mx: " << mx << "\n";
    getMaxes(t, from + 1, b, m, mx);
    m.push_back(b);
    /*
    std::cout << "m (b): [";
    for (auto i : m) {
        std::cout << i << ", ";
    }
    std::cout << "]\n";
    */
    for (int i = 1; i < m.size() - 1; ++i) {
        int a = ans(vec, m[i - 1] + 1, m[i + 1], m[i], t);
        if (a > ret) {
            ret = a;
        }
    }
    //std::cout << "returning " << ret + 1 << "\n";
    return ret + 1;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<uint64_t> vec;
    vec.reserve(n);
    for (int i = 0; i < n; ++i) {
        uint64_t k;
        std::cin >> k;
        if (i == 0 || vec[vec.size() - 1] != k)
            vec.push_back(k);
    }
    n = vec.size();
    auto tree = mkMaxtree(vec, 0, n);
    std::cout << ans(vec, 0, n, n, tree) - 1 << "\n";
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1 2 3 4 5 6 7 8 9 10

correct output
10

user output
10

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
10 9 8 7 6 5 4 3 2 1

correct output
10

user output
10

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
10 9 6 10 10 3 6 7 6 5

correct output
4

user output
4

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
51 90 27 98 85 47 14 55 82 52

correct output
6

user output
6

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
9 65 90 86 45 52 52 95 40 85

correct output
5

user output
5

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
3 46 77 16 59 32 22 41 87 89

correct output
7

user output
7

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1

user output
1

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
5000

user output
5000

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
5000
5000 4999 4998 4997 4996 4995 ...

correct output
5000

user output
5000

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
5000
10 8 10 5 4 9 2 9 10 10 1 2 7 ...

correct output
9

user output
9

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
5000
655923386 310000737 281882248 ...

correct output
28

user output
28

Test 13

Group: 2, 3

Verdict:

input
5000
123456789 123456790 123456791 ...

correct output
2706

user output
(empty)

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
5000
123456789 123456790 123456791 ...

correct output
5000

user output
5000

Test 15

Group: 3

Verdict: ACCEPTED

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1

user output
1

Test 16

Group: 3

Verdict: ACCEPTED

input
200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
200000

user output
200000

Test 17

Group: 3

Verdict: ACCEPTED

input
200000
200000 199999 199998 199997 19...

correct output
200000

user output
200000

Test 18

Group: 3

Verdict: ACCEPTED

input
200000
4 7 8 3 3 10 3 4 2 6 10 8 5 8 ...

correct output
10

user output
10

Test 19

Group: 3

Verdict: ACCEPTED

input
200000
824527039 112439661 517794857 ...

correct output
43

user output
43

Test 20

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
30764

user output
(empty)

Test 21

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
61367

user output
(empty)

Test 22

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
1

correct output
1

user output
1

Test 23

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 1

correct output
1

user output
1

Test 24

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 2

correct output
2

user output
2

Test 25

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
2 1

correct output
2

user output
2

Test 26

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2 1

correct output
2

user output
2

Test 27

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2 3

correct output
3

user output
3

Test 28

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
3 2 1

correct output
3

user output
3

Test 29

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 1 2

correct output
2

user output
2