weird issues with USACO median

I.5

1000 47506
70920
34639
63807
71201
40169
85943
98395
24541
46944
75780
57639
78073
68934
79648
36283
48725
83916
18403
71654
17114
2745
11388
94412
91234
49758
21751
66963
56682
10146
30062
4187
81065
81052
67993
68617
21220
70287
67011
62112
33583
59142
36103
28007
28076
15750
64289
93152
99666
99044
64805
16779
1788
92545
27542
93021
42302
49293
76336
15335
59438
22749
19521
56854
20152
3866
41823
41371
74152
8833
19835
24086
84327
55937
52092
28754
71686
32733
21905
87703
48128
3061
4481
49915
95605
48375
59287
54258
97667
35622
85944
73456
74722
5465
46661
94873
25682
88483
52596
16185
13668
88782
40271
97994
44718
8714
43099
32755
57798
81355
20458
5925
84415
41290
55839
96372
89664
31478
66981
87330
83451
52925
77137
58173
74741
23798
69397
422
28632
38344
32958
42299
27125
89580
56644
88194
98294
99742
20949
56091
81096
57758
62016
81863
99047
34206
94586
88711
65683
61566
92392
65486
30842
85881
23658
5582
26030
9406
22355
54661
47750
71665
96960
74874
61244
53603
63068
59537
69697
368
31980
67144
58125
10347
49006
57171
60904
43591
62233
42939
21509
54625
8424
68702
40505
48433
74284
82886
57838
12990
37546
5587
84654
34505
80461
62250
4460
59880
21786
74156
60247
70117
41299
18371
96815
6657
91893
57719
66599
54126
657
88107
25102
25432
56809
81958
73864
47444
64843
31701
76785
2388
53640
77791
36893
34100
40040
41352
10331
78177
31859
70577
48294
73157
5299
61460
79813
97191
19178
62764
51316
36186
50870
76417
61617
24030
58374
35480
87825
23216
83533
64610
25604
37172
58752
78848
87623
98791
36551
97953
76967
68409
68529
41612
57917
90179
3072
54082
87369
38601
16845
55037
74787
84066
31453
36403
8096
6179
88235
12272
45746
71767
93233
87701
25290
51984
82900
12912
67126
19450
10864
44093
4210
95744
2056
62127
85922
5127
32560
89642
43728
49404
44678
34866
33469
92483
87620
57916
15013
75854
86540
60758
63972
79772
64811
5613
48108
47710
18524
15233
83512
45739
59325
87721
57834
77733
66199
43755
82859
98758
49749
42938
64513
94426
77803
97982
86908
81775
72249
18272
73980
58788
95382
37952
38560
60192
59916
86667
7901
78440
1899
7764
40530
77576
95485
98364
55308
78035
58470
54518
76793
8218
13808
41305
2644
91610
55638
5903
89736
27887
24175
63716
3026
19556
18019
41585
96099
77934
44603
20351
72725
62854
28115
13255
56781
39951
11618
28440
17985
70087
82957
11129
78305
96764
68786
97300
4726
24423
19554
94461
68661
60080
58176
71687
95987
92546
29623
92085
70480
90578
12436
43204
53431
56902
72810
10211
96852
84427
38650
14836
70866
37958
42317
65522
51074
11102
79173
55799
51876
98726
66611
20537
58806
41139
8575
71144
33684
54549
63229
20515
45126
92016
80071
98556
48917
52880
25118
62120
53659
80119
93307
24524
34429
35623
6397
85502
46724
85569
41300
14952
84294
24262
51840
59451
65400
60414
30595
15436
14962
10175
35950
60088
18542
16020
74995
83810
85252
16465
45929
38910
96583
39235
79785
47363
74858
86181
32864
37933
71749
90515
52884
72394
14777
4723
48197
96528
81488
78791
11963
12802
5317
64265
89241
23858
96636
80587
7667
81887
97051
69947
37148
9986
9181
16932
57348
84038
3112
90212
38323
91212
80726
91206
63606
11854
12281
28154
8382
93768
23296
36696
22921
28612
960
12161
68821
13948
92748
92839
12186
89798
62785
49334
16135
71965
82617
73483
72355
85729
80046
10677
93292
60771
18234
73249
72625
46866
1402
97358
40634
24697
34053
79906
53308
51365
92067
38480
65312
1166
31318
93849
7315
94102
43182
23450
66067
25799
13284
54773
27879
93329
81801
21170
70451
34
94419
59427
46900
12172
56784
3885
36869
90837
83790
6528
58553
92208
45008
23864
93373
76325
17712
17040
70427
77246
40489
52845
19396
70124
23969
47274
63452
5769
84795
50254
5802
95565
9681
69053
7737
66464
89289
60957
73652
73079
67484
32204
81638
12491
72419
91363
5168
6483
8402
91946
80
65242
61142
19475
35365
85110
83100
15168
90878
67894
65421
13031
79811
75101
98436
3899
57917
87724
64855
47920
77154
32338
96476
58792
61181
68894
66506
82700
91728
74907
74645
91807
40148
35786
11281
91864
37247
94380
7031
44476
78626
72451
73858
74788
47552
72293
78686
21820
76369
43540
69739
53522
92229
66214
28665
69761
51460
95170
52460
43187
86428
27104
51346
42927
79241
78978
34790
16487
89710
58172
77314
84687
30623
51172
59474
94526
39816
38159
32697
16184
98050
2435
86058
90278
85001
14722
60039
36460
26244
12498
95998
29023
55954
63695
71950
35194
42673
23091
68033
32382
81263
45346
17068
28237
12869
92893
22762
52685
31051
55458
68868
29100
74244
54925
35729
59244
85999
95767
12055
28594
24617
8053
57616
80570
71747
45917
32115
30771
69008
16499
79504
66622
78197
12923
94858
91065
5815
33971
43749
36865
5780
28969
82316
80023
83893
18045
55619
86243
13811
67673
31188
54779
92077
88804
51700
80176
34720
167
10946
20079
16665
90450
86700
94861
3372
97909
85926
9187
31879
46026
62403
54010
74994
44719
34033
58887
62763
6003
61481
92925
73675
92669
64056
82104
97824
15755
62279
48895
15921
73224
68974
32586
80025
72025
43798
99749
69934
46075
25287
18164
92101
87689
72174
67094
48759
22558
42332
27873
28560
3813
37150
2234
12833
1205
84337
10656
16959
62967
59550
32880
52543
44875
81817
32567
16900
41966
48667
3185
88041
73953
21348
80141
77994
9873
47234
43104
32430
89566
70977
60989
9730
8126
79575
22562
25682
80263
33217
42640
43230
9118
91871
95772
53993
90039
44690
70892
32005
93357
90428
20045
83661
11775
16537
78006
21648
63770
21110
70429
69687
8438
31418
79416
32915
10992
18329
58596
7606
67897
1235
67187
77015
9458
62958
47359
15848
24000
34602
47852
33708
25029
84248
33720
53155
17136
11726
74802
80906
32835
61583
66944
41272
93000
46360
74186
20343
81040
49133
27948
48937
50367
95135
42303
76176
74444
89661
92024
14795
24262
56227
48502
65642
40475
82222
18796
57610
10299
9950
54867
59485
71532
21811
17108
64531
84522
7645
1225
81913
56777
45524
30849
23495
40658
89503
99671
31454
79163
91694
46248
19776
64272
11102
85417
21098
9675
4213
95060
19973
14162
49926
95809
2045
88088
12916
66575
88961
20560
84151

median.cpp

#include <fstream>
#include <iostream>
#include <vector>
#include <cstdio>
#include <assert.h>
using namespace std;

#define loop(i, N) for(int i = 0; i != N; i++)
#define NMAX 100010

ifstream fin("I.5");
ifstream fout("O.5");

long long N, X;
int acc[NMAX];
int ans = 0;

void merge(int low, int mid, int high){
    // one block from [low --> mid] and one from [mid + 1 --> high]
    // sizes (mid - low + 1), and (high - mid)
    // this one actually changes their places on the original array

    // create new temp vectors, syntax is (start polong longer, end+1 polong longer)
    vector<int> lower(acc + low, acc + mid + 1);
    vector<int> higher(acc + mid + 1, acc + high + 1);

    assert(lower.size() == mid - low + 1);
    assert(higher.size() == high - mid);

    loop(i, lower.size()){
        assert(lower[i] == acc[low + i]);
    }
    loop(i, higher.size()){
        assert(higher[i] == acc[mid + 1 + i]);
    }


    int i = 0; // for lower
    int j = 0; // for higher

    for (int index = low; index <= high && i < lower.size() && j < higher.size(); index++){
        if (lower[i] <= higher[j]){
            // don't increment, just add stuff from the lower
            acc[index] = lower[i];
            i++;
        }
        else {
            // lines will cross
            acc[index] = higher[j];
            ans += (mid - low - i) + 1;
            //cout << low << ' ' << mid << ' ' << high << " | " << i << " | " << (mid - low + 1 - i) << '\n';
            j++;
        }
    }
}


void mergesort(int low, int high){
    // pass indexes to the array acc in, and merge sort those sections
    // thses are inclusive array indices
    if(low >= high){
        return;
    }

    int mid = (low + high)/2;
    mergesort(low, mid);
    mergesort(mid + 1, high);
    merge(low, mid, high);
}

int main()
{   
    fin >> N >> X;

    long long temp;
    acc[0] = 0;

    for (int i = 1; i != N+1; i++){
        fin >> temp;
        acc[i] = acc[i-1] + (temp >= X ? 1 : -1);
    }

    // now figure out how many pairs of numbers i, j are there
    // such that acc[j] >= acc[i] and j > i. That suffices.
    
    mergesort(0, N);

    fout >> temp;
    cout << temp << " : ";
    cout << ((N)*(N+1))/2 - ans;
    return 0;
}

O.5

478319