Submission details
Task:Sort
Sender:RJuknevicius
Submission time:2026-04-17 14:38:12 +0300
Language:C++ (C++20)
Status:READY
Result:13
Feedback
subtaskverdictscore
#1ACCEPTED6
#20
#3ACCEPTED7
#40
#50
#60
#70
Test results
testverdicttimesubtask
#10.00 s2, 6, 7details
#2ACCEPTED0.00 s1, 2, 3, 6, 7details
#30.00 s2, 6, 7details
#4ACCEPTED0.00 s1, 2, 3, 6, 7details
#5ACCEPTED0.00 s1, 2, 3, 6, 7details
#6ACCEPTED0.00 s1, 2, 3, 6, 7details
#7ACCEPTED0.00 s1, 2, 3, 6, 7details
#8ACCEPTED0.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
#140.00 s2, 6, 7details
#150.00 s2, 6, 7details
#16ACCEPTED0.65 s3, 7details
#17ACCEPTED0.67 s3, 7details
#18ACCEPTED0.65 s3, 7details
#19ACCEPTED0.66 s3, 7details
#20ACCEPTED0.65 s3, 7details
#21ACCEPTED0.64 s3, 7details
#22ACCEPTED0.65 s3, 7details
#23ACCEPTED0.73 s3, 7details
#240.66 s4, 7details
#250.78 s4, 7details
#260.51 s4, 7details
#271.11 s4, 7details
#280.51 s4, 7details
#290.51 s4, 7details
#300.02 s5, 6, 7details
#310.02 s5, 6, 7details
#320.02 s5, 6, 7details
#330.03 s5, 6, 7details
#340.03 s5, 6, 7details
#350.02 s5, 6, 7details
#360.02 s6, 7details
#370.03 s6, 7details
#380.03 s6, 7details
#390.03 s6, 7details
#400.03 s6, 7details
#410.02 s6, 7details
#420.77 s7details
#430.76 s7details
#440.76 s7details
#450.86 s7details
#460.87 s7details
#470.87 s7details
#480.90 s7details
#491.06 s7details
#500.85 s7details
#510.85 s7details
#52ACCEPTED0.00 s1, 2, 3, 5, 6, 7details
#53ACCEPTED0.00 s1, 2, 3, 4, 5, 6, 7details
#540.00 s2, 5, 6, 7details
#55ACCEPTED0.00 s1, 2, 3, 4, 6, 7details
#56ACCEPTED0.00 s1, 2, 3, 6, 7details
#570.00 s6, 7details
#58ACCEPTED0.21 s3, 4, 7details
#59ACCEPTED0.21 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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:98:18: warning: unused variable 'la' [-Wunused-variable]
   98 |              int la=twocount[n-b-1], lala=twocount[n-1]-twocount[a-1];
      |                  ^~
input/code.cpp:98:38: warning: unused variable 'lala' [-Wunused-variable]
   98 |              int la=twocount[n-b-1], lala=twocount[n-1]-twocount[a-1];
      |                                      ^~~~

Code

#include <bits/stdc++.h>
using namespace std;
int lmin[200000], rmin[200000], lmax[200000], rmax[200000], x[200000], xs[200000], tw[800001], wrong[200000], twocount[200000];

void wrongbuild(int v, int tl, int tr)
{
    if(tl>tr) return;
    if(tl==tr) {tw[v]=wrong[tl];return;}

    int tm=(tl+tr)/2;
    wrongbuild(2*v, tl, tm);
    wrongbuild(2*v+1, tm+1, tr);
    tw[v]=tw[2*v]+tw[2*v+1];

}

int wrongquery(int v, int tl, int tr, int l, int r)
{
    if(tl>tr || tl>r || tr<l) return 0;
    if(tl>=l && tr<=r) return tw[v];

    int tm=(tl+tr)/2;

    return wrongquery(2*v, tl, tm, l, r) + wrongquery(2*v+1, tm+1, tr, l,r);
}



int main()
{
    int n, q;
    cin>>n>>q;

    for(int i = 0; i < n; i++)
    {
        cin>>x[i];
        xs[i]=x[i];

        if(i==0) {lmin[i]=x[i];lmax[i]=x[i];}
        else {
            if(x[i-1]>x[i]) wrong[i]=1;
            lmin[i]=min(lmin[i-1], x[i]);
            lmax[i]=max(lmax[i-1], x[i]);
            twocount[i]=twocount[i-1];
        }
        if(x[i]==2) twocount[i]++;
    }
    sort(xs, xs+n);
    rmax[n-1]=x[n-1];
    rmin[n-1]=x[n-1];
    for(int i = n-2; i >=0; i--)
    {

        rmin[i]=min(rmin[i+1], x[i]);
        rmax[i]=max(rmax[i+1], x[i]);

    }

    wrongbuild(1, 0, n-1);

    for(int uzklausa = 0; uzklausa < q;uzklausa++)
    {
        int a,b;cin>>a>>b;
        if(a+b<n)
        {
            if(wrongquery(1, 0, n-1, a, n-b-1)!=0) cout  <<-1 << endl;
            else
            {
                if(x[a]<lmax[a-1] || x[n-b-1] > rmin[n-b]) cout  <<-1 << endl;
                else  cout << (!(wrongquery(1, 0, n-1, 0, a-1)==0)) + (!(wrongquery(1, 0, n-1, n-b, n-1)==0)) << endl;
            }
        }
        if(a+b==n)
        {
            if(lmax[a-1]<=rmin[a])
            {
                cout << (!(wrongquery(1, 0, n-1, 0, a-1)==0)) + (!(wrongquery(1, 0, n-1, a, n-1)==0)) << endl;
            }
            else cout << -1 << endl;
        }
        if(a+b>n)
        {
            int z= !(wrongquery(1, 0 , n-1, 0, n-1)==0);
            if(z==0) cout << 0 << endl;
             if(a==n || b==n) {cout << min(1, z) << endl;continue;}
             /*int A=0;
             for(int i = 0; i <n-b;i++)
             {
                 if(x[i] > rmin[a]) A++;
             }
             int B=0;
             for(int i = a; i <n;i++)
             {
                 if(x[i]<lmax[n-b-1]) B++;
             }*/
             if(twocount[n-b-1]==0) cout << 1 << endl;
             if(twocount[n-1]-twocount[a-1]==n-a) cout << 1 << endl;
             int la=twocount[n-b-1], lala=twocount[n-1]-twocount[a-1];

             if(twocount[a-1]/(a+b-n)==twocount[n-b-1]/(a+b-n))
             {
                 cout << 2*((twocount[a-1]+a+b-n-1)/(a+b-n))-1 << endl;
            }
             else
            {
                 cout << 2*((twocount[a-1])/(a+b-n)) + (twocount[n-1]<n-a ? 1 : 0) << endl;
             }

             /*int dal=a+b-n;
             cout << max(2*max(A/dal+(A%dal!=0), B/dal+(B%dal!=0)-1 + (A/dal==B/dal ? 1 : 0) - (A!=B && min(A%dal, B%dal)==0 ? 1 : 0)), max((!wrongquery(1, 0, n-1, 0, n-b-1)==0) + (!wrongquery(1, 0, n-1, a, n-1)==0), z)) << endl;*/
             //cout << (!wrongquery(1, 0, n-1, 0, a-1)==0) + (!wrongquery(1, 0, n-1, n-b, n-1)==0) << endl;
        }
    }
}

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
-1

Feedback: Output is longer than expected

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:

input
1 1
417021999
1 1

correct output
0

user output
0
0

Feedback: Output is longer than expected

Test 4

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
20751947 20751947 20751947 494...

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

user output
-1
-1
1
1
-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: ACCEPTED

input
10 10
237541216 237541216 35036522 6...

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

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

Test 8

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
319425549 513116712 539199939 ...

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

user output
-1
-1
-1
-1
-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
-1
-1
1
1
-1
...

Feedback: Output is longer than expected

Test 12

Subtask: 2, 6, 7

Verdict:

input
10 10
679842175 48724877 720966351 6...

correct output
2
3
2
1
1
...

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

Feedback: Output is longer than expected

Test 13

Subtask: 2, 6, 7

Verdict:

input
10 10
893310183 811950921 338863962 ...

correct output
2
1
1
2
5
...

user output
1
-1
1
1
1
...

Feedback: Output is longer than expected

Test 14

Subtask: 2, 6, 7

Verdict:

input
10 10
221045363 282395847 441913686 ...

correct output
0
0
0
0
0
...

user output
0
1
-1
0
0
...

Feedback: Output is longer than expected

Test 15

Subtask: 2, 6, 7

Verdict:

input
10 10
509019662 983949268 960017302 ...

correct output
3
-1
3
3
3
...

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

Feedback: Output is longer than expected

Test 16

Subtask: 3, 7

Verdict: ACCEPTED

input
200000 200000
2277053 2277053 2277053 227705...

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

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

Test 17

Subtask: 3, 7

Verdict: ACCEPTED

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

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

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

Test 18

Subtask: 3, 7

Verdict: ACCEPTED

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

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

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

Test 19

Subtask: 3, 7

Verdict: ACCEPTED

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

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

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

Test 20

Subtask: 3, 7

Verdict: ACCEPTED

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

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

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

Test 21

Subtask: 3, 7

Verdict: ACCEPTED

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

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

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

Test 22

Subtask: 3, 7

Verdict: ACCEPTED

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

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

user output
-1
-1
-1
-1
-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
-1
1
1
-1
-1
...

Feedback: Output is longer than expected

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
1
1
1
-1
1
...

Feedback: Output is longer than expected

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
3
2
1
1
7
...

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

Test 27

Subtask: 4, 7

Verdict:

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
1
-1
0
...

Feedback: Output is longer than expected

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
8513
1101
35941
66289
19597
...

Feedback: Incorrect character on line 2 col 2: expected "1099", got "1101"

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
178347
196567
62117
97989
64891
...

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

Test 30

Subtask: 5, 6, 7

Verdict:

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
...

Feedback: Output is longer than expected

Test 31

Subtask: 5, 6, 7

Verdict:

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
1
-1
1
-1
...

Feedback: Output is longer than expected

Test 32

Subtask: 5, 6, 7

Verdict:

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
1
-1
-1
-1
...

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

Test 33

Subtask: 5, 6, 7

Verdict:

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

correct output
3
3
3
3
11
...

user output
1
-1
1
1
1
...

Feedback: Output is longer than expected

Test 34

Subtask: 5, 6, 7

Verdict:

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
1
0
1
0
...

Feedback: Output is longer than expected

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
1
-1
1
-1
-1
...

Feedback: Output is longer than expected

Test 36

Subtask: 6, 7

Verdict:

input
5000 5000
202010 457852 826471 926337 10...

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

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

Feedback: Output is longer than expected

Test 37

Subtask: 6, 7

Verdict:

input
5000 5000
190583 326486 431922 462939 72...

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

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

Feedback: Output is longer than expected

Test 38

Subtask: 6, 7

Verdict:

input
5000 5000
821998255 400550008 71790232 5...

correct output
5
3
3
2
5
...

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

Feedback: Output is longer than expected

Test 39

Subtask: 6, 7

Verdict:

input
5000 5000
266174928 446601941 191252234 ...

correct output
3
3
414
4
3
...

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

Feedback: Output is longer than expected

Test 40

Subtask: 6, 7

Verdict:

input
5000 5000
11621 243915 243915 949123 137...

correct output
0
0
0
0
0
...

user output
0
1
-1
0
1
...

Feedback: Output is longer than expected

Test 41

Subtask: 6, 7

Verdict:

input
5000 5000
999767052 998555066 997822810 ...

correct output
919
459
505
833
809
...

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

Feedback: Output is longer than expected

Test 42

Subtask: 7

Verdict:

input
200000 200000
478025 478025 478025 478025 47...

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

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

Feedback: Output is longer than expected

Test 43

Subtask: 7

Verdict:

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

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

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

Feedback: Output is longer than expected

Test 44

Subtask: 7

Verdict:

input
199531 200000
11328 26391 30353 37063 44412 ...

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

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

Feedback: Output is longer than expected

Test 45

Subtask: 7

Verdict:

input
200000 200000
106738201 369187074 412614650 ...

correct output
2
12
3
19
3
...

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

Feedback: Output is longer than expected

Test 46

Subtask: 7

Verdict:

input
200000 200000
670611290 43427363 8475380 309...

correct output
3
5
3
3
3
...

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

Feedback: Output is longer than expected

Test 47

Subtask: 7

Verdict:

input
200000 200000
907542569 504758282 948727805 ...

correct output
3
33
3
3
3
...

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

Feedback: Output is longer than expected

Test 48

Subtask: 7

Verdict:

input
200000 200000
487056731 460461648 142698485 ...

correct output
3
3
3
3
3
...

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

Feedback: Output is longer than expected

Test 49

Subtask: 7

Verdict:

input
200000 200000
12772 23236 23236 23236 41149 ...

correct output
0
0
0
0
0
...

user output
0
1
-1
0
1
...

Feedback: Output is longer than expected

Test 50

Subtask: 7

Verdict:

input
200000 200000
999993539 999993361 999993361 ...

correct output
125375
16687
-1
84781
46147
...

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

Feedback: Output is longer than expected

Test 51

Subtask: 7

Verdict:

input
200000 200000
999993539 999993361 999993361 ...

correct output
94788
177608
95881
56377
179957
...

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

Feedback: Output is longer than expected

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:

input
4 1
2 1 4 3
3 2

correct output
2

user output
1

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

Test 55

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

Verdict: ACCEPTED

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
...

Test 56

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
181777772 181777772 181777772 ...

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

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

Test 57

Subtask: 6, 7

Verdict:

input
100 10
92800811 524548163 939127795 9...

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

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

Feedback: Output is longer than expected

Test 58

Subtask: 3, 4, 7

Verdict: ACCEPTED

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
...

Test 59

Subtask: 3, 7

Verdict: ACCEPTED

input
100 100000
172695325 172695325 172695325 ...

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

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

Test 60

Subtask: 2, 6, 7

Verdict:

input
4 10
869194539 239439572 968540665 ...

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

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

Feedback: Output is longer than expected

Test 61

Subtask: 2, 6, 7

Verdict:

input
10 10
55366041 112170735 112170735 5...

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

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

Feedback: Output is longer than expected

Test 62

Subtask: 2, 6, 7

Verdict:

input
10 10
156018639 156018639 445832758 ...

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

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

Feedback: Output is longer than expected

Test 63

Subtask: 2, 6, 7

Verdict:

input
10 10
702507512 702507512 892090406 ...

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

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

Feedback: Output is longer than expected

Test 64

Subtask: 2, 6, 7

Verdict:

input
10 10
720324490 720324490 720324490 ...

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

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

Feedback: Output is longer than expected