Submission details
Task:Sort
Sender:jsesok
Submission time:2026-09-30 14:14:33 +0300
Language:C++ (C++23)
Status:READY
Result:0
Feedback
subtaskverdictscore
#10
#20
#30
#40
#50
#60
#70
Test results
testverdicttimesubtask
#10.00 s2, 6, 7details
#2ACCEPTED0.00 s1, 2, 3, 6, 7details
#3ACCEPTED0.00 s2, 6, 7details
#40.00 s1, 2, 3, 6, 7details
#5ACCEPTED0.00 s1, 2, 3, 6, 7details
#6ACCEPTED0.00 s1, 2, 3, 6, 7details
#70.00 s1, 2, 3, 6, 7details
#80.00 s1, 2, 3, 6, 7details
#9ACCEPTED0.00 s1, 2, 3, 6, 7details
#10ACCEPTED0.00 s1, 2, 3, 6, 7details
#110.00 s2, 6, 7details
#120.00 s2, 6, 7details
#130.00 s2, 6, 7details
#14ACCEPTED0.00 s2, 6, 7details
#150.00 s2, 6, 7details
#160.09 s3, 7details
#170.09 s3, 7details
#180.09 s3, 7details
#190.09 s3, 7details
#200.09 s3, 7details
#210.09 s3, 7details
#220.09 s3, 7details
#23ACCEPTED0.08 s3, 7details
#24--4, 7details
#25--4, 7details
#26--4, 7details
#27ACCEPTED0.08 s4, 7details
#28--4, 7details
#29--4, 7details
#30ACCEPTED0.09 s5, 6, 7details
#31ACCEPTED0.09 s5, 6, 7details
#32ACCEPTED0.09 s5, 6, 7details
#33ACCEPTED0.71 s5, 6, 7details
#34ACCEPTED0.01 s5, 6, 7details
#35--5, 6, 7details
#360.01 s6, 7details
#370.01 s6, 7details
#380.01 s6, 7details
#390.01 s6, 7details
#40ACCEPTED0.01 s6, 7details
#410.01 s6, 7details
#420.03 s7details
#430.03 s7details
#440.03 s7details
#450.03 s7details
#460.03 s7details
#470.03 s7details
#480.03 s7details
#49ACCEPTED0.09 s7details
#500.03 s7details
#510.03 s7details
#52ACCEPTED0.00 s1, 2, 3, 5, 6, 7details
#53ACCEPTED0.00 s1, 2, 3, 4, 5, 6, 7details
#54ACCEPTED0.00 s2, 5, 6, 7details
#550.00 s1, 2, 3, 4, 6, 7details
#560.00 s1, 2, 3, 6, 7details
#570.00 s6, 7details
#580.03 s3, 4, 7details
#590.03 s3, 7details
#600.00 s2, 6, 7details
#610.00 s2, 6, 7details
#620.00 s2, 6, 7details
#630.00 s2, 6, 7details
#640.00 s2, 6, 7details

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(0);
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    // badPref[i] = количество инверсий соседних пар в a[0..i]
    vector<int> badPref(n, 0), badSuf(n, 0);

    for (int i = 1; i < n; ++i) {
        badPref[i] = badPref[i - 1] + (a[i - 1] > a[i]);
    }

    for (int i = n - 2; i >= 0; --i) {
        badSuf[i] = badSuf[i + 1] + (a[i] > a[i + 1]);
    }

    bool allSorted = (badPref[n - 1] == 0);

    // Переиспользуем память между запросами
    vector<unsigned char> g(n + 1);

    while (q--) {
        int p, s;
        cin >> p >> s;

        if (allSorted) {
            cout << 0 << '\n';
            continue;
        }

        // =====================================================
        // НЕ ПЕРЕСЕКАЮТСЯ
        // =====================================================
        if (p + s <= n) {
            bool ok = true;

            // prefix должен содержать только значения <= p
            for (int i = 0; i < p; ++i) {
                if (a[i] > p) {
                    ok = false;
                    break;
                }
            }

            // неизменяемая середина должна уже стоять правильно
            if (ok) {
                for (int i = p; i < n - s; ++i) {
                    if (a[i] != i + 1) {
                        ok = false;
                        break;
                    }
                }
            }

            // suffix должен содержать только значения > n-s
            if (ok) {
                for (int i = n - s; i < n; ++i) {
                    if (a[i] <= n - s) {
                        ok = false;
                        break;
                    }
                }
            }

            if (!ok) {
                cout << -1 << '\n';
                continue;
            }

            int ans = 0;

            if (badPref[p - 1])
                ++ans;

            if (badSuf[n - s])
                ++ans;

            cout << ans << '\n';
            continue;
        }

        // =====================================================
        // ПЕРЕСЕКАЮТСЯ
        //
        // A | B | C
        //
        // A = [0,L)
        // B = [L,R)
        // C = [R,n)
        // =====================================================

        int L = n - s;
        int R = p;

        auto solve = [&](int first) -> int {
            // 0 = A
            // 1 = B
            // 2 = C

            for (int i = 0; i < L; ++i)
                g[a[i]] = 0;

            for (int i = L; i < R; ++i)
                g[a[i]] = 1;

            for (int i = R; i < n; ++i)
                g[a[i]] = 2;

            int maxA = n;
            int minB = 1;
            int maxB = n;
            int minC = 1;

            auto fixMaxA = [&]() {
                while (maxA >= 1 && g[maxA] != 0)
                    --maxA;
            };

            auto fixMinB = [&]() {
                while (minB <= n && g[minB] != 1)
                    ++minB;
            };

            auto fixMaxB = [&]() {
                while (maxB >= 1 && g[maxB] != 1)
                    --maxB;
            };

            auto fixMinC = [&]() {
                while (minC <= n && g[minC] != 2)
                    ++minC;
            };

            fixMaxA();
            fixMinB();
            fixMaxB();
            fixMinC();

            // Отсортированы ли сами три куска до операций.
            bool sortedA =
                (L <= 1 || badPref[L - 1] == 0);

            bool sortedC =
                (R >= n - 1 || badSuf[R] == 0);

            bool sortedB = true;

            if (R - L >= 2) {
                // Число плохих соседних пар внутри [L,R)
                int bad =
                    badPref[R - 1] -
                    (L == 0 ? 0 : badPref[L]);

                sortedB = (bad == 0);
            }

            // Максимум столько операций точно достаточно:
            // каждое полезное действие улучшает разбиение.
            for (int cnt = 1; cnt <= 2 * n + 2; ++cnt) {
                int type;

                if (cnt & 1)
                    type = first;
                else
                    type = first ^ 1;

                // =========================================
                // PREFIX
                // =========================================
                if (type == 0) {
                    fixMaxA();
                    fixMinB();

                    while (maxA >= 1 &&
                           minB <= n &&
                           maxA > minB) {

                        int x = maxA;
                        int y = minB;

                        // x: A -> B
                        // y: B -> A
                        g[x] = 1;
                        g[y] = 0;

                        /*
                            maxA может только уменьшиться.
                            minB может только увеличиться
                            внутри этой P-операции.

                            x, попавший в B, может увеличить maxB.
                        */

                        --maxA;
                        ++minB;

                        if (x > maxB)
                            maxB = x;

                        if (y < minC && g[y] == 2)
                            minC = y;

                        fixMaxA();
                        fixMinB();
                    }

                    sortedA = true;
                    sortedB = true;
                }

                // =========================================
                // SUFFIX
                // =========================================
                else {
                    fixMaxB();
                    fixMinC();

                    while (maxB >= 1 &&
                           minC <= n &&
                           maxB > minC) {

                        int x = maxB;
                        int y = minC;

                        // x: B -> C
                        // y: C -> B
                        g[x] = 2;
                        g[y] = 1;

                        /*
                            maxB уменьшается внутри S.
                            minC увеличивается.

                            y может уменьшить minB.
                        */

                        --maxB;
                        ++minC;

                        if (y < minB)
                            minB = y;

                        fixMaxB();
                        fixMinC();
                    }

                    sortedB = true;
                    sortedC = true;
                }

                // =========================================
                // Проверяем правильность групп
                // =========================================

                fixMaxA();
                fixMinB();
                fixMaxB();
                fixMinC();

                bool good = true;

                // A должно быть {1,...,L}
                if (L > 0 && maxA > L)
                    good = false;

                // B должно быть {L+1,...,R}
                if (R > L) {
                    if (minB <= L || maxB > R)
                        good = false;
                }

                // C должно быть {R+1,...,n}
                if (R < n && minC <= R)
                    good = false;

                if (good && sortedA && sortedB && sortedC)
                    return cnt;
            }

            return (int)1e9;
        };

        int ansP = solve(0); // P S P S ...
        int ansS = solve(1); // S P S P ...

        int ans = min(ansP, ansS);

        if (ans >= (int)1e9)
            cout << -1 << '\n';
        else
            cout << ans << '\n';
    }
}

Test details

Test 1

Subtask: 2, 6, 7

Verdict:

input
6 3
3 1 4 1 5 9
4 1
3 3
2 5

correct output
1
-1
2

user output
1
-1
-1

Feedback: Incorrect character on line 3 col 1: expected "2", got "-1"

Test 2

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
2 1
548813503 548813503
1 1

correct output
0

user output
0

Test 3

Subtask: 2, 6, 7

Verdict: ACCEPTED

input
1 1
417021999
1 1

correct output
0

user output
0

Test 4

Subtask: 1, 2, 3, 6, 7

Verdict:

input
10 10
20751947 20751947 20751947 494...

correct output
-1
-1
1
1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 3 col 1: expected "1", got "-1"

Test 5

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
12780811 19475241 19475241 683...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 6

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
14574963 14574963 14574963 864...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 7

Subtask: 1, 2, 3, 6, 7

Verdict:

input
10 10
237541216 237541216 35036522 6...

correct output
-1
-1
-1
2
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 4 col 1: expected "2", got "-1"

Test 8

Subtask: 1, 2, 3, 6, 7

Verdict:

input
10 10
319425549 513116712 539199939 ...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 6 col 1: expected "1", got "-1"

Test 9

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
54363219 54363219 110986323 11...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 10

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 5
55687086 550701455 326656159 5...

correct output
-1
-1
-1
-1
-1

user output
-1
-1
-1
-1
-1

Test 11

Subtask: 2, 6, 7

Verdict:

input
10 10
35889584 588130796 815837475 8...

correct output
-1
-1
1
1
1
...

user output
(empty)

Test 12

Subtask: 2, 6, 7

Verdict:

input
10 10
679842175 48724877 720966351 6...

correct output
2
3
2
1
1
...

user output
(empty)

Test 13

Subtask: 2, 6, 7

Verdict:

input
10 10
893310183 811950921 338863962 ...

correct output
2
1
1
2
5
...

user output
(empty)

Test 14

Subtask: 2, 6, 7

Verdict: ACCEPTED

input
10 10
221045363 282395847 441913686 ...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 15

Subtask: 2, 6, 7

Verdict:

input
10 10
509019662 983949268 960017302 ...

correct output
3
-1
3
3
3
...

user output
(empty)

Test 16

Subtask: 3, 7

Verdict:

input
200000 200000
2277053 2277053 2277053 227705...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 46 col 1: expected "2", got "-1"

Test 17

Subtask: 3, 7

Verdict:

input
200000 200000
6767 16596 16596 27202 37272 4...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 6 col 1: expected "1", got "-1"

Test 18

Subtask: 3, 7

Verdict:

input
200000 200000
5393 5910 9099 15755 15755 164...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 11 col 1: expected "2", got "-1"

Test 19

Subtask: 3, 7

Verdict:

input
200000 200000
3779 4629 8999 10468 22605 227...

correct output
-1
1
2
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 2 col 1: expected "1", got "-1"

Test 20

Subtask: 3, 7

Verdict:

input
200000 200000
878 2791 10849 11861 13405 239...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 13 col 1: expected "2", got "-1"

Test 21

Subtask: 3, 7

Verdict:

input
200000 200000
430 1479 1992 2829 7152 14093 ...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 98 col 1: expected "2", got "-1"

Test 22

Subtask: 3, 7

Verdict:

input
199997 200000
2733 10526 13882 14035 14689 3...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 20 col 1: expected "1", got "-1"

Test 23

Subtask: 3, 7

Verdict: ACCEPTED

input
200000 200000
12345 13538 15407 18490 18984 ...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 24

Subtask: 4, 7

Verdict:

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

correct output
-1
1
-1
-1
-1
...

user output
(empty)

Test 25

Subtask: 4, 7

Verdict:

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

correct output
1
-1
1
-1
1
...

user output
(empty)

Test 26

Subtask: 4, 7

Verdict:

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

correct output
4
3
2
2
6
...

user output
(empty)

Test 27

Subtask: 4, 7

Verdict: ACCEPTED

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

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 28

Subtask: 4, 7

Verdict:

input
200000 200000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

correct output
8513
1099
35939
9299
19597
...

user output
(empty)

Test 29

Subtask: 4, 7

Verdict:

input
200000 200000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

correct output
178345
169257
62115
96143
64796
...

user output
(empty)

Test 30

Subtask: 5, 6, 7

Verdict: ACCEPTED

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

correct output
1
1
-1
1
-1
...

user output
1
1
-1
1
-1
...

Test 31

Subtask: 5, 6, 7

Verdict: ACCEPTED

input
5000 5000
1 2 3 4 5 6 7 8 9 72 145 47 19...

correct output
-1
2
-1
2
-1
...

user output
-1
2
-1
2
-1
...

Test 32

Subtask: 5, 6, 7

Verdict: ACCEPTED

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

correct output
-1
2
-1
-1
-1
...

user output
-1
2
-1
-1
-1
...

Test 33

Subtask: 5, 6, 7

Verdict: ACCEPTED

input
5000 5000
4033 4368 3086 3208 4313 388 8...

correct output
3
3
3
3
11
...

user output
3
3
3
3
11
...

Test 34

Subtask: 5, 6, 7

Verdict: ACCEPTED

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

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 35

Subtask: 5, 6, 7

Verdict:

input
5000 5000
5000 4999 4998 4997 4996 4995 ...

correct output
2039
1910
-1
687
673
...

user output
(empty)

Test 36

Subtask: 6, 7

Verdict:

input
5000 5000
202010 457852 826471 926337 10...

correct output
-1
-1
2
-1
-1
...

user output
(empty)

Test 37

Subtask: 6, 7

Verdict:

input
5000 5000
190583 326486 431922 462939 72...

correct output
-1
-1
-1
-1
2
...

user output
(empty)

Test 38

Subtask: 6, 7

Verdict:

input
5000 5000
821998255 400550008 71790232 5...

correct output
5
3
3
2
5
...

user output
(empty)

Test 39

Subtask: 6, 7

Verdict:

input
5000 5000
266174928 446601941 191252234 ...

correct output
3
3
414
4
3
...

user output
(empty)

Test 40

Subtask: 6, 7

Verdict: ACCEPTED

input
5000 5000
11621 243915 243915 949123 137...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 41

Subtask: 6, 7

Verdict:

input
5000 5000
999767052 998555066 997822810 ...

correct output
919
459
505
833
809
...

user output
(empty)

Test 42

Subtask: 7

Verdict:

input
200000 200000
478025 478025 478025 478025 47...

correct output
-1
-1
2
2
2
...

user output
(empty)

Test 43

Subtask: 7

Verdict:

input
200000 200000
1810 2088 3022 3097 7459 7943 ...

correct output
2
-1
-1
2
-1
...

user output
(empty)

Test 44

Subtask: 7

Verdict:

input
199531 200000
11328 26391 30353 37063 44412 ...

correct output
-1
2
-1
2
2
...

user output
(empty)

Test 45

Subtask: 7

Verdict:

input
200000 200000
106738201 369187074 412614650 ...

correct output
2
12
3
19
3
...

user output
(empty)

Test 46

Subtask: 7

Verdict:

input
200000 200000
670611290 43427363 8475380 309...

correct output
3
5
3
3
3
...

user output
(empty)

Test 47

Subtask: 7

Verdict:

input
200000 200000
907542569 504758282 948727805 ...

correct output
3
33
3
3
3
...

user output
(empty)

Test 48

Subtask: 7

Verdict:

input
200000 200000
487056731 460461648 142698485 ...

correct output
3
3
3
3
3
...

user output
(empty)

Test 49

Subtask: 7

Verdict: ACCEPTED

input
200000 200000
12772 23236 23236 23236 41149 ...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 50

Subtask: 7

Verdict:

input
200000 200000
999993539 999993361 999993361 ...

correct output
125375
16687
-1
84781
46147
...

user output
(empty)

Test 51

Subtask: 7

Verdict:

input
200000 200000
999993539 999993361 999993361 ...

correct output
94788
177608
95881
56377
179957
...

user output
(empty)

Test 52

Subtask: 1, 2, 3, 5, 6, 7

Verdict: ACCEPTED

input
5 1
2 1 3 5 4
2 2

correct output
2

user output
2

Test 53

Subtask: 1, 2, 3, 4, 5, 6, 7

Verdict: ACCEPTED

input
2 1
1 2
1 1

correct output
0

user output
0

Test 54

Subtask: 2, 5, 6, 7

Verdict: ACCEPTED

input
4 1
2 1 4 3
3 2

correct output
2

user output
2

Test 55

Subtask: 1, 2, 3, 4, 6, 7

Verdict:

input
10 10
1 1 1 1 2 2 1 1 2 2
7 1
2 6
4 5
...

correct output
-1
1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 2 col 1: expected "1", got "-1"

Test 56

Subtask: 1, 2, 3, 6, 7

Verdict:

input
10 10
181777772 181777772 181777772 ...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 10 col 1: expected "1", got "-1"

Test 57

Subtask: 6, 7

Verdict:

input
100 10
92800811 524548163 939127795 9...

correct output
-1
-1
3
-1
3
...

user output
(empty)

Test 58

Subtask: 3, 4, 7

Verdict:

input
100 100000
2 2 2 1 2 2 2 2 1 2 1 1 1 2 2 ...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 1401 col 1: expected "1", got "-1"

Test 59

Subtask: 3, 7

Verdict:

input
100 100000
172695325 172695325 172695325 ...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Feedback: Incorrect character on line 417 col 1: expected "1", got "-1"

Test 60

Subtask: 2, 6, 7

Verdict:

input
4 10
869194539 239439572 968540665 ...

correct output
-1
2
-1
-1
-1
...

user output
(empty)

Test 61

Subtask: 2, 6, 7

Verdict:

input
10 10
55366041 112170735 112170735 5...

correct output
-1
-1
2
1
1
...

user output
(empty)

Test 62

Subtask: 2, 6, 7

Verdict:

input
10 10
156018639 156018639 445832758 ...

correct output
-1
1
-1
-1
2
...

user output
(empty)

Test 63

Subtask: 2, 6, 7

Verdict:

input
10 10
702507512 702507512 892090406 ...

correct output
-1
2
-1
2
2
...

user output
(empty)

Test 64

Subtask: 2, 6, 7

Verdict:

input
10 10
720324490 720324490 720324490 ...

correct output
-1
2
2
1
-1
...

user output
(empty)