6612번: Andrew the Ant

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


$O(ta\lg a)$


두 개미가 부딪혔을 때, 두 개미 모두 방향이 바뀌므로 서로를 통과해서 진행한다고 봐도 된다.
이런식으로 생각했을 때 모두 떨어지는데까지 걸린 시간은 처음 상황에서 방향이 바뀌지 않는 채로 진행했을 때 가장 오래 머무르는 개미의 이동 시간이다.

개미를 좌표 순으로 a1, a2, a3 ... an 이라고 하자.
모든 개미가 떨어질 때까지 이 개미들의 순서는 바뀔 수 없다. 따라서 처음 <- 방향 개미가 c개 존재했다면
a1, ..., ac 는 왼쪽에서 떨어지며 이 중에 ac가 가장 늦게 떨어진다.
ac+1, ... , an은 오른쪽에서 떨어지며 이 중에 ac+1이 가장 늦게 떨어진다.
처음에 통과한다고 가정해서 풀었을 때 <-방향 개미가 가장 늦게 떨어진다면 ac가 답이고 그 반대이면 ac+1이 답이다.
물론 늦게 떨어지는 개미가 둘이면 ac, ac+1 둘 다 답이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int l, a, x[100000];
int main() {
    while (~scanf("%d%d", &l, &a)) {
        int p = 0, ml = -1, mr = -1;
        char c;
        for (int i = 0; i < a; i++) {
            scanf("%d %c", x + i, &c);
            if (c == 'L') ml = max(ml, x[i]), p++;
            else mr = max(mr, l - x[i]);
        }
        sort(x, x + a);
        printf("The last ant will fall down in %d seconds - started at %d", max(ml, mr), ml < mr ? x[p] : x[p - 1]);
        if (ml == mr) printf(" and %d", x[p]);
        puts(".");
    }
    return 0;
}