[BOJ] 1665 화물열차

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

1665번: 화물열차

 

 

안만나는 경우

A의 시작과 B의 시작이 만나는 경우 (증가 폭 1)

A의 끝과 B의 시작이 만나는 경우 (증가폭 0)

 

A의 시작과 B의 끝이 만나는 경우 (증가 폭 -1)

 

A의 끝과 B의 끝이 만나는 경우 (증가 폭 0)

이렇게 총 5개의 상황이 벌어질 수 있고, 두 시작점이 만나는 시점부터 컨테이너가 만나는 칸 수가 늘어나다가, A의 시작이 B의 끝을 만나거나, A의 끝이 B의 시작을 만나는 경우가 생기면 칸 수가 유지되다가 하락한다. 그러다 두 끝점이 만나는 시점부터는 컨테이너가 만나는 칸 수가 0이 유지된다.

 

이 기울기 함수들을 누적합으로 관리해서 최대로 컨테이너 끼리 만나는 칸 수가 몇인지 구할 수 있다.

시간복잡도는 \(O(NMlogNM)\) 이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,m;
pi a[1005],b[1005];
vecpi vv;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> a[i].x >> a[i].y;
    }
    cin >> m;
    for(int i = 1;i <= m;i++) {
        cin >> b[i].x >> b[i].y;
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            vv.pb({a[i].x+b[j].x-1,1});
            vv.pb({a[i].x+b[j].y,-1});
            vv.pb({a[i].y+b[j].x,-1});
            vv.pb({a[i].y+b[j].y+1,1});
        }
    }
    sort(all(vv));
    int la = -INF;
    ll g = 0,val = 0,ans = 0,mo = 0;
    for(pi i : vv) {
        if(la != -INF) val += g*(i.x-la);
        g += i.y, la = i.x;
        if(ans < val) mo = i.x-1, ans = val;
    }
    cout << mo;
}