BOJ 9426: 중앙값 측정

작성일

https://www.acmicpc.net/problem/9426

  • 3월동안 210문제 풀기 (12/210)
  • Multimap이라는 치트를 써서 Running Median으로 어거지로 품
  • 실제로는 Segment Tree로 풀린다고 함.
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
97
98
99
#include <bits/stdc++.h>
using namespace std;

struct RunningMedian {
  multiset<int> minq, maxq;

  void push(int x) {
    if(maxq.empty() || maxq.size() == minq.size()) maxq.insert(x);
    else minq.insert(x);

    if(minq.size() && *maxq.rbegin() > *minq.begin()) {
      auto it = maxq.end(); it--;
      minq.insert(*it);
      maxq.erase(it);
      maxq.insert(*minq.begin());
      minq.erase(minq.begin());
    }
  }

  void remove(int x) {
    if(minq.empty() || x <= *maxq.rbegin()) {
      auto it = maxq.find(x);
      maxq.erase(it);
    } else {
      auto it = minq.find(x);
      minq.erase(it);
    }
    if(maxq.size()+1 == minq.size()) {
      maxq.insert(*minq.begin());
      minq.erase(minq.begin());
    }
    if(maxq.size() == 2+ minq.size()) {
      auto it = maxq.end(); it--;
      minq.insert(*it);
      maxq.erase(it);
    }
  }

  int median() {
    return *maxq.rbegin();
  }
};

#include <sys/stat.h>
#include <sys/mman.h>
class fio {
  size_t rsize;
  unsigned char* rbuf;
  int ridx;

  public:
  fio() : ridx(0) {
    struct stat rstat;
    fstat(0, &rstat);
    rsize = rstat.st_size;
    rbuf = (unsigned char*)mmap(0,rsize,PROT_READ,MAP_FILE|MAP_PRIVATE,0,0);
  }

  inline bool isBlank() {
    return
      rbuf[ridx] == '\n' || rbuf[ridx] == '\t' || rbuf[ridx] == '\r' ||
      rbuf[ridx] == '\f' || rbuf[ridx] == '\v' || rbuf[ridx] == ' ';
  }
  inline void consumeBlank() { while (isBlank()) ridx++; }

  inline int readInt(){
    int res = 0, flag = 0;
    consumeBlank();
    if (rbuf[ridx] == '-'){
      flag = 1;
      ridx++;
    }
    while (!isBlank() && ridx < rsize)
      res = 10 * res + rbuf[ridx++] - '0';
    return flag ? -res : res;
  }
};
fio io;

int main() {
  int N, K;
  vector<int> arr;
  N = io.readInt();
  K = io.readInt();
  RunningMedian rm;
  arr.reserve(N);
  for(int i = 0; i < N; i++)
    arr.push_back(io.readInt());
  for(int i = 0; i < K-1; i++)
    rm.push(arr[i]);

  long long ans = 0;
  for(int i = K-1; i < N; i++) {
    rm.push(arr[i]);
    ans += rm.median();
    rm.remove(arr[i-K+1]);
  }
  cout << ans;
}