BOJ 23295 - 스터디 시간 정하기 1

BOJ 23295 - 스터디 시간 정하기 1

iMOS 법을 써서 먼저 $T=100,000$ 까지의 구간을 쭉 칠해준 뒤, 슬라이딩 윈도우로 해당 구간에서 구간합이 가장 클 때를 구해주면 된다.

void solve() {
   int n, t;
   cin >> n >> t;
   vi psum(100005);
   for (int i = 0; i < n; i++) {
      int k;
      cin >> k;
      while (k--) {
         int s, e;
         cin >> s >> e;
         psum[s]++;
         psum[e]--;
      }
   }
   for (int i = 1; i <= 100000; i++)psum[i] += psum[i - 1];
   ll sum = 0;
   for (int i = 0; i < t; i++) sum += psum[i];
   ll ans = sum;
   pi a{0, t};
   for (int i = t; i <= 100000; i++) {
      sum -= psum[i - t];
      sum += psum[i];

      if (sum > ans) {
         ans = max(ans, sum);
         a = {i - t + 1, i + 1};
      }
   }
   cout << a.fi << ' ' << a.se;
}