백준 9426 [c++] 중앙값 측정

백준 9426 [c++] 중앙값 측정

#include < stdio.h >

int n, k;

long long ans;

long long st[ 1 < < 18 ];

int data[ 250001 ];

int pivot = 1 < < 17 ;

void update( int idx, int value){

st[idx] + = value;

idx > > = 1 ;

while (idx) {

st[idx] = st[idx * 2 ] + st[idx * 2 + 1 ];

idx > > = 1 ;

}

}

void query( int node, int from, int to, int val) {

if (from = = to) {

ans + = node - pivot;

return ;

}

if (st[node * 2 ] > = val)

query(node * 2 ,from,(from + to) / 2 ,val);

else

query(node * 2 + 1 , (from + to) / 2 + 1 ,to, val - st[node * 2 ]);

}

int main() {

scanf ( "%d%d" , & n, & k);

for ( int i = 0 ; i < n; i + + ) {

scanf ( "%d" , & data[i]);

update(data[i] + pivot, 1 );

if (i > = k - 1 ) {

query( 1 , 1 ,pivot,(k + 1 ) / 2 );

update(pivot + data[i - k + 1 ], - 1 );

}

}

printf ( "%lld" , ans);

return 0 ;

}

from http://kuony.tistory.com/10 by ccl(A) rewrite - 2021-08-09 22:26:18