https://jungol.co.kr/problem/2790

| 시간 제한 | 메모리 제한 |
| 1초 | 64MB |
문제
병호가 ‘L’백화점에서 ‘N’타이어를 팔려고 한다. 공장에서 출고한 타이어는 총 N종류 있다. 허나, 타이어들의 부피가 너무 크기 때문에 타이어를 운송할 때 타이어 안에 타이어를 끼우는 식으로 운송해야 한다.

병호가 ‘L’백화점에서 ‘N’타이어를 팔려고 한다. 공장에서 출고한 타이어는 총 N종류 있다. 허나, 타이어들의 부피가 너무 크기 때문에 타이어를 운송할 때 타이어 안에 타이어를 끼우는 식으로 운송해야 한다.
입력
첫 번째 줄에는 출고한 타이어의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄부터 N개의 줄에는 각 타이어의 안지름 I, 바깥지름 O, 가격 P가 주어진다.
1 ≤ I < O ≤ 1,000,000,000, 1 ≤ P ≤ 1,000 전체 데이터의 50%는 1 ≤ N ≤ 1,500이다.
출력
병호가 팔 수 있는 타이어의 가격의 합의 최댓값을 출력한다.
풀이
2584 전시장 (정올, python3)
https://jungol.co.kr/problem/2584시간 제한메모리 제한1초64MB문제전시장에서 그림을 판매하는 업체에 하나의 전시대가 배정된다. 전시될 그림은 직사각형의 모양을 가지고 있고, 그림의 높이는 다를 수
celbeing.tistory.com
이 문제에 좌표압축 섞어서 해결할 수 있습니다.
타이어 내경과 외경을 모두 포함한 직경 데이터를 좌표압축해서 0부터 최대 99,999까지의 데이터로 만듭니다. 이걸 가지고 세그먼트 트리를 만들 수 있습니다. 직경 `di`에 대해 `di`내에 채울 수 있는 타이어의 최대 가치를 `seg[di]`로 처리합시다.
타이어 정보를 외경을 기준으로 오름차순 정렬합니다. 순서대로 타이어를 확인하면, 내경보다 작은 외경을 가진 타이어는 모두 확인했으므로 `seg[inner_di]`는 가능한 모든 타이어를 확인한 상태로 정리되어있습니다. 즉, 이번에도 최댓값 세그먼트 트리를 활용해 현재 타이어의 내경 이하의 최적해에 현재 타이어의 가치를 더한 것을 `seg[outer_di]`에 저장하고 갱신합니다. 단, 이때 이미 들어있는 값이 현재 탐색한 값보다 크다면 갱신하지 않습니다.
정답 코드
좌표압축 전처리가 더 복잡하네요.
for i, o, p in tire:
t = query(i)+p
if seg[size+o] < t:
update(o, t)
print(seg[1])