BOJ 28284 - 스터디 카페

BOJ 28284 - 스터디 카페

일단 정렬하고 구간합 배열을 구성해둔다.

큰 것부터 $k$개와 작은것부터 $k$개를 뽑은 것의 합을 바로 구할 수 있게 전처리해두면 된다.

그런다음 $S_i, E_i$ 를 모두 $(S_i,+1), (E_i+1, -1)$ 처럼 이벤트로 바꿔서 시간순으로 정렬한다음

특정 시간 구간에 사람이 몇명이 있는지를 스위핑해주면 풀 수 있다.

void solve() {
   int n, m;
   cin >> n >> m;
   vi a(n);
   fv(a);
   sort(all(a), greater<>());
   vi mx(n);
   mx[0] = a[0];
   for (int i = 1; i < n; i++) mx[i] = mx[i - 1] + a[i];
   vector<pi> evt;
   vi T;
   for (int i = 0; i < m; i++) {
      int l, r;
      cin >> l >> r;
      T.pb(l), T.pb(r + 1);
      evt.pb({l, 1});
      evt.pb({r + 1, -1});
   }
   uniq(T);
   sort(all(evt));
   int p = 0;
   ll ans = 0, ans2 = 0;
   T.pb(T.back() + 1);
   for (int t = 0, j = 0; t < sz(T) - 1; t++) {
      int added = 0, removed = 0;

      while (j < sz(evt) && evt[j].fi <= T[t]) {
         if (evt[j].se == 1) added++;
         else removed++;
         j++;
      }
      p += added - removed;

      int dt = T[t + 1] - T[t];
      if (p) {
         ans += 1ll * dt * mx[p - 1];
         ans2 += 1ll * dt * (mx[n - 1] - (n - 1 - p >= 0 ? mx[n - 1 - p] : 0));
      }
   }
   cout << ans2 << ' ' << ans;
}