— Dark mode

BOI 2026 Mirror Day 2

Sort

  • Start: 2026-04-17 10:00:00
  • End: 2026-04-17 15:00:00
Submission details
Task:Sort
Sender:jsesok
Submission time:2026-10-01 13:32:45 +0300
Language:C++ (C++23)
Status:READY
Result:6
Feedback
subtaskverdictscore
#1ACCEPTED6
#20
#30
#40
#50
#60
#70
Test results
testverdicttimesubtask
#1ACCEPTED0.00 s2, 6, 7details
#2ACCEPTED0.00 s1, 2, 3, 6, 7details
#3ACCEPTED0.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
#14ACCEPTED0.00 s2, 6, 7details
#150.00 s2, 6, 7details
#16--3, 7details
#17--3, 7details
#18--3, 7details
#19--3, 7details
#20--3, 7details
#21--3, 7details
#22--3, 7details
#23--3, 7details
#24--4, 7details
#25--4, 7details
#26--4, 7details
#27--4, 7details
#28--4, 7details
#29--4, 7details
#300.48 s5, 6, 7details
#310.55 s5, 6, 7details
#320.61 s5, 6, 7details
#331.39 s5, 6, 7details
#34ACCEPTED0.45 s5, 6, 7details
#350.53 s5, 6, 7details
#360.62 s6, 7details
#370.66 s6, 7details
#381.36 s6, 7details
#391.40 s6, 7details
#40ACCEPTED0.47 s6, 7details
#410.58 s6, 7details
#42--7details
#43--7details
#44--7details
#45--7details
#46--7details
#47--7details
#48--7details
#49--7details
#50--7details
#51--7details
#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.03 s3, 4, 7details
#59ACCEPTED0.03 s3, 7details
#600.00 s2, 6, 7details
#610.00 s2, 6, 7details
#620.00 s2, 6, 7details
#630.01 s2, 6, 7details
#640.00 s2, 6, 7details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:44:15: warning: unused variable 'm' [-Wunused-variable]
   44 |     int n, q, m, p, s, l=-1, sum, ba, bb, bam, bbm, d, can, sq, left, right;
      |               ^
input/code.cpp:44:56: warning: unused variable 'can' [-Wunused-variable]
   44 |     int n, q, m, p, s, l=-1, sum, ba, bb, bam, bbm, d, can, sq, left, right;
      |                                                        ^~~

Code

#include <iostream>
#include <numeric>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <random>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
int cal(int ba, int bb, int bam, int bbm, int d)
{
    bb-=bbm;
    ba-=d;
    if (max(ba, bb)<=0)
    {
        return 2;
    }
    ba=(ba+d-1)/d;
    bb=(bb+d-1)/d;
    if (bb<=ba)
    {
        return 2+ba*2;
    }
    else if (bb==ba+1)
    {
        return 2+2*bb-1;
    }
    else
    {
        return 2+bb*2;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, m, p, s, l=-1, sum, ba, bb, bam, bbm, d, can, sq, left, right;
    cin>>n>>q;
    sq=sqrt(n);
    vector<int> ma(n), mi(n), a(n), r(n+1), kop, sor, ans(q), kiek, kiek2(n);
    set<int> num;
    vector<pair<int, int>> v;
    vector<tuple<int, int, int, int>> mo;
    for (int i=0; i<n; ++i)
    {
        cin>>a[i];
        v.push_back({a[i], i});
    }
    sort(v.begin(), v.end());
    for (int i=0; i<n; ++i)
    {
        a[v[i].second]=i+1;
    }
    for (int i=0; i<n; ++i)
    {
        num.insert(a[i]);
        kiek.push_back(i-distance(num.begin(), upper_bound(num.begin (), num.end(), i+1))+1);
    }
    num={};
    for (int i=n-1; i>=0; --i)
    {
        num.insert(a[i]);
        kiek2[i]=distance(num.begin(), lower_bound(num.begin(), num.end(), i+1));
    }
    kop=a;
    sor=a;
    sort(sor.begin(), sor.end());
    ma[0]=a[0];
    for (int i=1; i<n; ++i)
        ma[i]=max(a[i], ma[i-1]);
    mi[n-1]=a[n-1];
    for (int i=n-2; i>=0; --i)
    {
        mi[i]=min(a[i], mi[i+1]);
    }
    for (int i=0; i<n; ++i)
    {
        if (l>=i)
        {
            r[i]=l;
        }
        else
        {
            l=i;
            for (int j=i+1; j<n; ++j)
            {
                if (a[j-1]>a[j])
                    break;
                l=j;
            }
            r[i]=l;
        }
    }
    r[n]=n-1;
    for (int j=0; j<q; ++j)
    {
        cin>>p>>s;
        if (p+s<=n)
        {
            sum=0;
            if (ma[p-1]>mi[p] || r[p]<n-s-1 || mi[n-s]<ma[n-s-1])
            {
                ans[j]=-1;
                continue;
            }
            if (r[0]<p-1)
                sum+=1;
            if (r[n-s]!=n-1)
                sum+=1;
            ans[j]=sum;
        }
        else
        {
            mo.push_back({(n-s)/sq, p, s, j});
        }
    }
    sort(mo.begin(), mo.end());
    num={};
    for (int i=0; i<(int) mo.size(); ++i)
    {
        p=get<1>(mo[i]);
        s=get<2>(mo[i]);
        if (i==0)
        {
            left=n-s;
            right=p;
            for (int j=n-s; j<p; ++j)
            {
                num.insert(a[j]);
            }
        }
        else
        {
            if (left>n-s)
            {
                for (int j=n-s; j<left; ++j)
                {
                    num.insert(a[j]);
                }
            }
            else
            {
                for (int j=left; j<n-s; ++j)
                {
                    num.erase(a[j]);
                }
            }
            if (right>p)
            {
                for (int j=p; j<right; ++j)
                {
                    num.erase(a[j]);
                }
            }
            else
            {
                for (int j=right; j<p; ++j)
                {
                    num.insert(a[j]);
                }
            }
            left=n-s;
            right=p;
        }
        if (r[0]==n-1)
        {
            ans[get<3>(mo[i])]=0;
            continue;
        }
        if (kiek[p-1]==0 || kiek2[n-s]==0)
        {
            ans[get<2>(mo[i])]=1;
            continue;
        }
        d=s+p-n;
        ba=kiek[p-1];
        bb=kiek2[n-s];
        bam=d-distance(num.begin(), upper_bound(num.begin (), num.end(), p));
        bbm=distance(num.begin(), lower_bound(num.begin (), num.end(), n-s+1));
        ans[get<3>(mo[i])]=min(cal(ba, bb, bam, bbm, d), cal(bb, ba, bbm, bam, d));
    }
    for (int i=0; i<q; ++i)
    {
        cout<<ans[i]<<"\n";
    }
    return 0;
}

Test details

Test 1

Subtask: 2, 6, 7

Verdict: ACCEPTED

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

correct output
1
-1
2
view save

user output
1
-1
2
view save

Test 2

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
2 1
548813503 548813503
1 1
view save

correct output
0
view save

user output
0
view save

Test 3

Subtask: 2, 6, 7

Verdict: ACCEPTED

input
1 1
417021999
1 1
view save

correct output
0
view save

user output
0
view save

Test 4

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
20751947 20751947 20751947 494...
view save

correct output
-1
-1
1
1
-1
...
view save

user output
-1
-1
1
1
-1
...
view save

Test 5

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
12780811 19475241 19475241 683...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Test 6

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
14574963 14574963 14574963 864...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Test 7

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
237541216 237541216 35036522 6...
view save

correct output
-1
-1
-1
2
-1
...
view save

user output
-1
-1
-1
2
-1
...
view save

Test 8

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
319425549 513116712 539199939 ...
view save

correct output
-1
-1
-1
-1
-1
...
view save

user output
-1
-1
-1
-1
-1
...
view save

Test 9

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
54363219 54363219 110986323 11...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Test 10

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 5
55687086 550701455 326656159 5...
view save

correct output
-1
-1
-1
-1
-1
view save

user output
-1
-1
-1
-1
-1
view save

Test 11

Subtask: 2, 6, 7

Verdict:

input
10 10
35889584 588130796 815837475 8...
view save

correct output
-1
-1
1
1
1
...
view save

user output
-1
-1
1
0
1
...
view save

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

Test 12

Subtask: 2, 6, 7

Verdict:

input
10 10
679842175 48724877 720966351 6...
view save

correct output
2
3
2
1
1
...
view save

user output
(empty)

Error:
free(): invalid pointer

Test 13

Subtask: 2, 6, 7

Verdict:

input
10 10
893310183 811950921 338863962 ...
view save

correct output
2
1
1
2
5
...
view save

user output
(empty)

Error:
free(): invalid pointer

Test 14

Subtask: 2, 6, 7

Verdict: ACCEPTED

input
10 10
221045363 282395847 441913686 ...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Test 15

Subtask: 2, 6, 7

Verdict:

input
10 10
509019662 983949268 960017302 ...
view save

correct output
3
-1
3
3
3
...
view save

user output
(empty)

Error:
free(): invalid pointer

Test 16

Subtask: 3, 7

Verdict:

input
200000 200000
2277053 2277053 2277053 227705...
view save

correct output
-1
-1
-1
-1
-1
...
view save

user output
(empty)

Test 17

Subtask: 3, 7

Verdict:

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

correct output
-1
-1
-1
-1
-1
...
view save

user output
(empty)

Test 18

Subtask: 3, 7

Verdict:

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

correct output
-1
-1
-1
-1
-1
...
view save

user output
(empty)

Test 19

Subtask: 3, 7

Verdict:

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

correct output
-1
1
2
-1
-1
...
view save

user output
(empty)

Test 20

Subtask: 3, 7

Verdict:

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

correct output
-1
-1
-1
-1
-1
...
view save

user output
(empty)

Test 21

Subtask: 3, 7

Verdict:

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

correct output
-1
-1
-1
-1
-1
...
view save

user output
(empty)

Test 22

Subtask: 3, 7

Verdict:

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

correct output
-1
-1
-1
-1
-1
...
view save

user output
(empty)

Test 23

Subtask: 3, 7

Verdict:

input
200000 200000
12345 13538 15407 18490 18984 ...
view save

correct output
0
0
0
0
0
...
view save

user output
(empty)

Test 24

Subtask: 4, 7

Verdict:

input
200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

correct output
-1
1
-1
-1
-1
...
view save

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

correct output
1
-1
1
-1
1
...
view save

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

correct output
4
3
2
2
6
...
view save

user output
(empty)

Test 27

Subtask: 4, 7

Verdict:

input
200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

correct output
0
0
0
0
0
...
view save

user output
(empty)

Test 28

Subtask: 4, 7

Verdict:

input
200000 200000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
view save

correct output
8513
1099
35939
9299
19597
...
view save

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

correct output
178345
169257
62115
96143
64796
...
view save

user output
(empty)

Test 30

Subtask: 5, 6, 7

Verdict:

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

correct output
1
1
-1
1
-1
...
view save

user output
0
0
-1
0
-1
...
view save

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

Test 31

Subtask: 5, 6, 7

Verdict:

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

correct output
-1
2
-1
2
-1
...
view save

user output
-1
0
-1
0
-1
...
view save

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

Test 32

Subtask: 5, 6, 7

Verdict:

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

correct output
-1
2
-1
-1
-1
...
view save

user output
-1
2
-1
-1
-1
...
view save

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

Test 33

Subtask: 5, 6, 7

Verdict:

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

correct output
3
3
3
3
11
...
view save

user output
3
3
3
3
11
...
view save

Feedback: Incorrect character on line 289 col 3: expected "217", got "216"

Test 34

Subtask: 5, 6, 7

Verdict: ACCEPTED

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

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Test 35

Subtask: 5, 6, 7

Verdict:

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

correct output
2039
1910
-1
687
673
...
view save

user output
2040
1910
1
687
1
...
view save

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

Test 36

Subtask: 6, 7

Verdict:

input
5000 5000
202010 457852 826471 926337 10...
view save

correct output
-1
-1
2
-1
-1
...
view save

user output
-1
-1
2
-1
-1
...
view save

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

Test 37

Subtask: 6, 7

Verdict:

input
5000 5000
190583 326486 431922 462939 72...
view save

correct output
-1
-1
-1
-1
2
...
view save

user output
-1
-1
-1
-1
2
...
view save

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

Test 38

Subtask: 6, 7

Verdict:

input
5000 5000
821998255 400550008 71790232 5...
view save

correct output
5
3
3
2
5
...
view save

user output
5
3
3
2
5
...
view save

Feedback: Incorrect character on line 153 col 3: expected "133", got "132"

Test 39

Subtask: 6, 7

Verdict:

input
5000 5000
266174928 446601941 191252234 ...
view save

correct output
3
3
414
4
3
...
view save

user output
3
3
414
4
3
...
view save

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

Test 40

Subtask: 6, 7

Verdict: ACCEPTED

input
5000 5000
11621 243915 243915 949123 137...
view save

correct output
0
0
0
0
0
...
view save

user output
0
0
0
0
0
...
view save

Test 41

Subtask: 6, 7

Verdict:

input
5000 5000
999767052 998555066 997822810 ...
view save

correct output
919
459
505
833
809
...
view save

user output
918
458
505
1
1
...
view save

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

Test 42

Subtask: 7

Verdict:

input
200000 200000
478025 478025 478025 478025 47...
view save

correct output
-1
-1
2
2
2
...
view save

user output
(empty)

Test 43

Subtask: 7

Verdict:

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

correct output
2
-1
-1
2
-1
...
view save

user output
(empty)

Test 44

Subtask: 7

Verdict:

input
199531 200000
11328 26391 30353 37063 44412 ...
view save

correct output
-1
2
-1
2
2
...
view save

user output
(empty)

Test 45

Subtask: 7

Verdict:

input
200000 200000
106738201 369187074 412614650 ...
view save

correct output
2
12
3
19
3
...
view save

user output
(empty)

Test 46

Subtask: 7

Verdict:

input
200000 200000
670611290 43427363 8475380 309...
view save

correct output
3
5
3
3
3
...
view save

user output
(empty)

Test 47

Subtask: 7

Verdict:

input
200000 200000
907542569 504758282 948727805 ...
view save

correct output
3
33
3
3
3
...
view save

user output
(empty)

Test 48

Subtask: 7

Verdict:

input
200000 200000
487056731 460461648 142698485 ...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 49

Subtask: 7

Verdict:

input
200000 200000
12772 23236 23236 23236 41149 ...
view save

correct output
0
0
0
0
0
...
view save

user output
(empty)

Test 50

Subtask: 7

Verdict:

input
200000 200000
999993539 999993361 999993361 ...
view save

correct output
125375
16687
-1
84781
46147
...
view save

user output
(empty)

Test 51

Subtask: 7

Verdict:

input
200000 200000
999993539 999993361 999993361 ...
view save

correct output
94788
177608
95881
56377
179957
...
view save

user output
(empty)

Test 52

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

Verdict: ACCEPTED

input
5 1
2 1 3 5 4
2 2
view save

correct output
2
view save

user output
2
view save

Test 53

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

Verdict: ACCEPTED

input
2 1
1 2
1 1
view save

correct output
0
view save

user output
0
view save

Test 54

Subtask: 2, 5, 6, 7

Verdict:

input
4 1
2 1 4 3
3 2
view save

correct output
2
view save

user output
0
view save

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

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

correct output
-1
1
-1
-1
-1
...
view save

user output
-1
1
-1
-1
-1
...
view save

Test 56

Subtask: 1, 2, 3, 6, 7

Verdict: ACCEPTED

input
10 10
181777772 181777772 181777772 ...
view save

correct output
-1
-1
-1
-1
-1
...
view save

user output
-1
-1
-1
-1
-1
...
view save

Test 57

Subtask: 6, 7

Verdict:

input
100 10
92800811 524548163 939127795 9...
view save

correct output
-1
-1
3
-1
3
...
view save

user output
-1
-1
3
-1
3
...
view save

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

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

correct output
-1
-1
-1
-1
-1
...
view save

user output
-1
-1
-1
-1
-1
...
view save

Test 59

Subtask: 3, 7

Verdict: ACCEPTED

input
100 100000
172695325 172695325 172695325 ...
view save

correct output
-1
-1
-1
-1
-1
...
view save

user output
-1
-1
-1
-1
-1
...
view save

Test 60

Subtask: 2, 6, 7

Verdict:

input
4 10
869194539 239439572 968540665 ...
view save

correct output
-1
2
-1
-1
-1
...
view save

user output
-1
0
1
-1
1
...
view save

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

Test 61

Subtask: 2, 6, 7

Verdict:

input
10 10
55366041 112170735 112170735 5...
view save

correct output
-1
-1
2
1
1
...
view save

user output
(empty)

Error:
free(): invalid pointer

Test 62

Subtask: 2, 6, 7

Verdict:

input
10 10
156018639 156018639 445832758 ...
view save

correct output
-1
1
-1
-1
2
...
view save

user output
(empty)

Error:
free(): invalid pointer

Test 63

Subtask: 2, 6, 7

Verdict:

input
10 10
702507512 702507512 892090406 ...
view save

correct output
-1
2
-1
2
2
...
view save

user output
-1
2
-1
0
1
...
view save

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

Test 64

Subtask: 2, 6, 7

Verdict:

input
10 10
720324490 720324490 720324490 ...
view save

correct output
-1
2
2
1
-1
...
view save

user output
-1
0
1
0
-1
...
view save

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

Tasks

A Distances-B Hamilton-C Sort-

Submissions (jsesok)

2026-10-02 18:22:46 1002026-10-02 18:20:30 132026-10-01 20:30:02 1002026-10-01 20:28:42 182026-10-01 19:44:09 182026-10-01 19:39:51 462026-10-01 19:33:04 532026-10-01 19:21:41 132026-10-01 19:08:01 132026-10-01 19:06:51 132026-10-01 18:05:35 132026-10-01 16:32:19 532026-10-01 16:13:49 532026-10-01 16:08:12 532026-10-01 16:06:20 132026-10-01 15:24:12 462026-10-01 15:21:57 62026-10-01 15:13:33 62026-10-01 15:09:49 62026-10-01 14:14:44 62026-10-01 14:13:12 62026-10-01 14:11:37 62026-10-01 13:32:45 62026-10-01 13:12:11 62026-09-30 17:21:33 532026-09-30 17:09:55 362026-09-30 16:43:51 132026-09-30 14:28:07 232026-09-30 14:14:33 02026-09-30 14:13:47 02026-09-30 14:09:57 02026-09-30 14:07:50 02026-09-30 14:03:26 132026-09-30 13:12:38 132026-09-30 12:57:17 132026-09-29 22:09:36 132026-09-29 18:02:57 132026-09-29 17:28:37 132026-09-23 16:40:09 132026-09-23 16:36:45 02026-04-17 10:38:55 112026-04-17 10:35:02 02026-04-17 10:33:57 02026-04-17 10:33:57 02026-04-17 10:22:01 6