PS/1572.cpp at main · smsh0722/PS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/* smsh0722
 * 1572
 * 중앙값
 * */
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_IN = 66536;

int updateST( int* ST, int idx, int l, int r, int trgIdx, int gap );
int getMedianST( int* ST, int idx, int l, int r, int curRank, int trgRank );

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    int* ST;
    {
        int h = ceil( log2(MAX_IN + 1 ) );
        int size = (2<<(h+1))-1;
        ST = new int[size];
        memset( ST, 0, sizeof(int)*size );
    }

    queue<int> old_data;
    for ( int i = 0; i < K; i++ ){
        int val;
        cin >> val;
        updateST( ST, 0, 0, MAX_IN, val, 1 );
        old_data.push(val);
    }

    int64_t sum = 0;
    // Solve
    {
        const int median_rank = (K+1)/2;
        int val;

        // Cal sum
        sum += int64_t( getMedianST( ST, 0, 0, MAX_IN, 0, median_rank ) );
        for ( int i = 0; i < N - K; i++ ){
            // Pop Data
            updateST( ST, 0, 0, MAX_IN, old_data.front(), -1 );
            old_data.pop();

            // Push Data
            cin >> val;
            updateST( ST, 0, 0, MAX_IN, val, 1 );
            old_data.push(val);

            // Cal sum
            sum += int64_t( getMedianST( ST, 0, 0, MAX_IN, 0, median_rank ) );
        }
    }

    // Print Result
    cout << sum;
    return 0;
}

int updateST( int* ST, int idx, int l, int r, int trgIdx, int gap )
{
    if ( l == r && l == trgIdx ){
        ST[idx] += gap;
        return ST[idx];
    }
    if ( trgIdx < l || r < trgIdx )
        return ST[idx];

    int mid = ( r - l ) / 2 + l;
    int lval = updateST( ST, idx*2+1, l, mid, trgIdx, gap );
    int rval = updateST( ST, idx*2+2, mid+1, r, trgIdx, gap );

    ST[idx] = (lval + rval);

    return ST[idx];
}
int getMedianST( int* ST, int idx, int l, int r, int curRank, int trgRank )
{
    if ( l == r )
        return l;

    int lval = ST[idx*2+1];
    int rval = ST[idx*2+2];
    int mid = ( r - l )/ 2 + l;
    if ( (curRank + lval) >= trgRank )
        return getMedianST( ST, idx*2+1, l, mid, curRank, trgRank );
    else
        return getMedianST( ST, idx*2+2, mid+1, r, curRank + lval, trgRank );
}