크레인 배차
골드 I의견: 0
어느 항만의 부두에는 \(N\)개의 크레인이 일렬로 늘어서 있다. 왼쪽부터 \(1\)번부터 \(N\)번까지 번호가 매겨져 있고, \(i\)번 크레인이 한 번에 들 수 있는 최대 무게는 \(a_i\)이다.
관제소는 두 종류의 명령을 처리한다.
- 성능 변경 : 어떤 크레인의 최대 적재량을 새 값으로 바꾼다.
- 배차 : 무게 \(x\)인 컨테이너가 \(l\)번 위치에 도착했다. \(l\)번 이상의 크레인 중 \(x\) 이상을 들 수 있는 가장 번호가 작은 크레인에 배정한다. 그런 크레인이 없으면 \(-1\)을 보고한다.
\(Q\)개의 명령을 순서대로 처리하여라.
\(1 \le N, Q \le 100\,000\)
\(0 \le a_i, v, x \le 10^9\)
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
이후 \(Q\)개의 줄에 각각 명령이 주어진다.
1 i v: \(i\)번 크레인의 적재량을 \(v\)로 바꾼다. (\(1 \le i \le N\))2 l x: \(l\)번 이상의 크레인 중 적재량이 \(x\) 이상인 가장 작은 번호를 출력한다. (\(1 \le l \le N\))
각 배차 명령(2)에 대해 답을 한 줄에 하나씩 출력한다. 조건을 만족하는 크레인이 없으면 \(-1\).
6 5
2 5 1 8 3 4
2 1 6
2 3 9
1 3 10
2 1 9
2 5 44
-1
3
6처음 \(1\)번 이상에서 \(6\) 이상은 \(4\)번(\(8\)). \(3\)번 이상에서 \(9\) 이상은 없어 \(-1\). \(3\)번을 \(10\)으로 바꾼 뒤 \(1\)번 이상에서 \(9\) 이상인 최소 번호는 \(3\)번이다. \(5\)번 이상에서 \(4\) 이상은 \(6\)번(\(4\)).
1 2
5
2 1 5
2 1 61
-1크레인이 하나뿐. 적재량 \(5\)이므로 \(5\) 이상 요청은 \(1\)번, \(6\) 이상 요청은 \(-1\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
크레인 배차
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
크레인 배차