핵심 아이디어

<aside> 💡

imos를 사용한다.

</aside>

기존 배열을 $a$라고 하면 $imos$배열은 $imos_i = a_i-a_{i-1}$가 된다.

이때 구간에 $1$을 더하는 쿼리는 시작지점에 $+1$ 끝+1지점에 $-1$을 하면 된다.

쿼리가 끝난 후 $imos$의 누적합 배열은 $a$배열이 된다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int N, T;
vector<pair<int, int>> se[100'001];

int imos[100'002];

signed main()
{
    FASTIO;
    cin >> N >> T;
    for(int i = 0; i<N; i++){
        int k; cin >> k;
        for(int j = 0; j<k; j++){
            int s,e; cin >> s >> e;
            imos[s]++;
            imos[e]--;
        }
    }

    ll now = 0LL;
    for(int i = 0; i<=100'000; i++){
        now += imos[i];
        imos[i] = now;
    }

    ll cur = 0LL;
    for(int i = 0; i<T; i++){
        cur += imos[i];
    }
    
    ll mx = cur;
    int anss = 0, anse = T;

    int eidx = T;
    for(int i = 0; i<=100'000-T; i++){
        cur -= imos[i];
        cur += imos[eidx++];

        if(cur > mx){
            mx = cur;
            anss = i+1;
            anse = eidx;
        }
    }
    cout << anss <<" " <<anse <<"\\n";
    // cout << mx <<"\\n";
    
    return 0;
}