# ABC188 D - Snuke Prime

ABC188 D - Snuke Prime

질문으로 연결

https://atcoder.jp/contests/abc188/tasks/abc188_d

문제 개요

주식회사는 각양각색의 서비스를 제공한다.각 서비스의 사용료는 c이다오늘이 나의 첫날첫날부터 b이튿날까지 사용할 예정입니다.프리미엄 서비스에 가입하면 매일 C엔을 내면 추가 비용 없이 모든 서비스를 이용할 수 있다.서비스를 이용하기 위해 지불해야 할 최소한의 합계 금액을 계산하다.

구속

1\leqq N\leqq 2 × 10^5
1\leqq C\leqq 10^9
1\leqq a_i\leqq b_i\leqq 10^9
1\leqq c_i\leqq 10^9

ABC의 답.

어느 날 서비스 이용료가 C를 초과했는지 계산하는 문제.브러쉬로 해도 돼요?생각하다i의 최대치가 10^9이기 때문에 이 크기의 배열을 준비해서 for링TLE을 돌리려고 한다(겸사겸사 자기 컴퓨터로 해봤는데 다운된 것 같아서 급하게 강제로 끝냈다).
이어 예전에 연이어 발생한 구간의 문제를 떠올리며 지인과 소회전을 벌여 문제를 확인한 결과ABC179 D - Leaping Tak를 발견했다.나는 잠시 해설을 보더니, "응, 이건 아니지. 하지만 이렇게 계산하면 양이 떨어지겠지."라고 말했다.(이렇게 반할 때도 있다. 경쟁자의 흥미로운 점이기도 하다.)
기분 전환을 위해 집안일을 하고 나서.× 10^5이기 때문에 실제 서비스 이용 금액이 달라지는 경우가 많습니다.× 2 × 10^5를 생각하고 좌표압축(좌압)을 해서 서비스 이용 금액을 구하고 좌압 전점 간의 거리와 서비스 이용 금액을 합계 금액을 구한다.시간이 좀 걸렸지만 AC

N, C = map(int, input().split())  # N個のサービス, すぬけプライムの値段C円

# a, b, c   i番目のサービスはa日のはじめからb日の終わりまでつかう。１日あたりc円かかる
# いもす法？10**9は配列にすると多すぎるから各サービスのa,bのみに圧縮する？それなら多くても2*10**5 * 2個でOK

ABC = []
dates = set([])
for _ in range(N):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    dates.add(a)
    dates.add(b)
    dates.add(b + 1)
dates = sorted(dates)

dic1 = {}
dic2 = {}
for i, date in enumerate(dates):
    dic1[i] = date
    dic2[date] = i

V = [0] * len(dates)
for a, b, c in ABC:
    V[dic2[a]] += c
    V[dic2[b + 1]] += -c
for i in range(1, len(V)):
    V[i] = V[i] + V[i - 1]

ans = 0
for i in range(len(V) - 1):
    diff = dic1[i + 1] - dic1[i]
    ans += min(V[i] * diff, C * diff)
print(ans)

공식 해법 1

구간뿐만 아니라 시작과 끝이라는 두 가지 점만 주목하고 다음과 같은 사건으로 간주한다(참고로 ABC의 답안에서 ai-1, bi 대신 첫날은 ai, bi+1일로 처리한다)

a_i-1일목과 a일차 비용은 ci엔화의 평가절상 사건이 발생하다

b_i일차 및 b1일 비용은 ci엔화 가치 하락 사건 발생

이렇게 하면 제 ABC의 답과 같은 이벤트가 많아요.× 2 × 10^5는 O(NlogN)로 풀 수 있습니다.
해답을 읽지 않는 코드가 문장만 읽고 실행할 때 a, b가 같은 값을 어떻게 정리하는지 몰라요.코드를 본 후 이벤트 시작 시간(아래 코드에서 x)의 값이 다르기 전에fee에 추가된 처리는 나를 매우 탄복하게 했다(그리고 이를 위해 이벤트를 정렬했다).나는 이렇게 처리하는 것을 잘하지 못하기 때문에 기억하고 싶다.

N, C = map(int, input().split())

events = []
for _ in range(N):
    a, b, c = map(int, input().split())
    events.append((a - 1, c))
    events.append((b, -c))
events.sort()

ans = 0
fee = 0
t = 0
for x, y in events:
    if x != t:
        ans += min(C, fee) * (x - t)
        t = x
    fee += y
print(ans)

https://atcoder.jp/contests/abc188/submissions/19416296

공식 해법 2

공식 해법 2는 내 ABC의 답안과 마찬가지로 좌압법을 한다.하지만 제 좌압은 두 개의 사전을 사용해 강제로 처리했기 때문에 예쁘지 않았고, 안개 씨가 트위터에 소개한 좌압은 이해하기 쉬웠기 때문에 참고해서 다시 실시했습니다.
앞으로 이걸 사용하게 해주세요.

N, C = map(int, input().split())

events = []
services = []
for _ in range(N):
    a, b, c = map(int, input().split())
    a -= 1
    events.append(a)
    events.append(b)
    services.append((a, b, c))

sorted_events = sorted(set(events))
D = {e: i for i, e in enumerate(sorted_events)}
compressed_events = [D[e] for e in sorted_events]

V = [0] * len(compressed_events)
for a, b, c in services:
    V[D[a]] += c
    V[D[b]] -= c

for i in range(1, len(V)):
    V[i] = V[i] + V[i - 1]

ans = 0
for i in range(len(V) - 1):
    diff = sorted_events[i + 1] - sorted_events[i]
    ans += min(C, V[i]) * diff
print(ans)

https://atcoder.jp/contests/abc188/submissions/19416697