BOJ 10556 KAMIONI

문제

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

10556번: KAMIONI

어떤 한 트럭이 수직선 상에서 A1, A2, A3, A4, ... , An (A1>A2<A3>A4 ... or A1<A2>A3<A4 ... ) 순으로 좌표를 따라 1초에 1m씩 이동한다. 이때 두 트럭 a, b가 주어졌을 때 두 트럭이 같은 위치에 있는 횟수를 구해야 한다. (단, 방향을 바꿀 때는 같은 위치가 아님이 보장된다.) ($N, Q<=10^5$, 3초)

 

풀이

IOI Regions trick 을 사용한다. 이를 위하여 다음의 꼴을 확인해보자.

 

쿼리로 a, b가 주어졌을 때 한 쿼리를 처리하는 시간이 $O(min(A, B))$ or $O(min(A, B)log A)$

 

두 트럭의 이동 경로를 s-t 그래프로 표현하면 다음과 같은 45도로 꺾인 그래프가 나온다.

 

wlog A<B 라 하면 A의 한 선분 세그먼트에서 2개 이상의 교점이 나오는 것은 불가능하다.

따라서 중간값 정리와 같이 선분의 시작과 끝의 y좌표 값을 비교하여 부호가 다르다면 1개의 교점이 존재한다는 뜻이다.

 

이를 이용하여 이분탐색으로 $A<B$ 일때 $O(AlgB)$ 안에 문제를 해결할 수 있다.

이제 이것을 NAIVE 하게 풀면 $O(QAlgB) = O(NQlgN)$ 이니 TLE가 나온다.

 

경우를 나눠보자. ($A<B$)

1. $A<sqrt(N)$ NAIVE 처리

2. $sqrt(N)<A$, B NAIVE 처리하고 메모이제이션한다.

A의 합은 N이니, $sqrt(N)<A$ 인 $A$의 수는 최대 $sqrt(N)$ 개이다.

따라서 map 에 메모이제이션하면 1번 경우는 $O(sqrt(N)lgN)$, 2번 경우는 $O(NlgN * sqrt(N))$ 안에 처리할 수 있다.

 

시간 복잡도 : $O(Qsqrt(N)lgN + NlgNsqrt(N))$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, M, SQ=400;
vector<ll> A[MAXN+10], T[MAXN+10];
map<pii, int> memo;

int f(ll x, int p)
{
    int i, j;
    int t=lower_bound(T[p].begin(), T[p].end(), x)-T[p].begin();

    if(t==0) return A[p][0];
    return A[p][t-1]+(A[p][t-1]<A[p][t]?1:-1)*(x-T[p][t-1]);
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=1; i<=N; i++)
    {
        int S;
        scanf("%d", &S);
        while(S--)
        {
            int t;
            scanf("%d", &t);
            if(A[i].size()==0) T[i].push_back(0);
            else T[i].push_back(T[i].back()+abs(A[i].back()-t));
            A[i].push_back(t);
        }
    }

    while(M--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(A[a].size()>A[b].size()) swap(a, b);

        if(A[a].size()>SQ) if(memo.find({a, b})!=memo.end()) { printf("%d\n", memo[{a, b}]); continue; }

        int ans=0;
        for(i=0; i+1<A[a].size(); i++)
        {
            ll s=T[a][i], e=min(T[b].back(), T[a][i+1]);
            if(s>=e) break;
            int fs=f(s, b), fe=f(e, b);
            fs=A[a][i]-fs;
            if(e==T[a][i+1]) fe=A[a][i+1]-fe;
            else fe=f(e, a)-fe;
            fs/=abs(fs);
            fe/=abs(fe);

            if(fs*fe<0) ans++;
        }
        if(A[a].size()>SQ) memo[{a, b}]=ans;
        printf("%d\n", ans);
    }
}