백준 23877 / C++

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

23877번: Convoluted Intervals

 

[ 풀이 ]

N제한에 비해 M은 5000이므로 O(M^2)까진 가능하다. 

구하는 값은 ai+aj<=k<=bi+bj인 (i,j)의 개수이다. 여사건으로

n^2- (ai+aj>k || bi+bj<k)를 구하자. 여기서 핵심은 ai+aj보다 bi+bj가 항상 크므로

ai+aj>k 와 bi+bj<k를 셀 때 중복이 일어나지 않는다는 점이다.

따라서 구하는 값은 n^2-(ai+aj>K)-(bi+bj<K) 이다.

값이 몇개 나오는지 배열을 만들고 세주면 aI+aj=K와 bI+bj=k는 쉽게 세줄 수 있다. 

이제 a합과 b합에 대해 누적합으로 전처리후 계산해도 좋고 

S(k+1)-S(k)=(ai+aj=k+1) -(bi+bj=K)임을 이용해도 좋다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, x, y;
ll L[10001], R[10001], A[5001], B[5001];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        A[x]++, B[y]++;
    }
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) {
            L[i + j] += A[i] * A[j];
            R[i + j] += B[i] * B[j];
        }
    }
    ll ans = 0;
    for (int i = 0; i <= 2 * m; i++) {
        ans += L[i];
        cout << ans << '\n';
        ans -= R[i];
    }
}