ohwphil   2년 전

한 미술관이 재정적 문제에 직면하여 소유하고 있는 $N$ 장의 그림을 판매하기로 결정했습니다. 각 그림에는 나이를 나타내는 $S_i$가 있습니다 – 그림이 만들어진 이후로 경과한 일수입니다. 구매 권리는 오래된 수집가인 미르코와 슬라브코가 얻었고, 구매를 더 흥미롭게 만들기 위해 다음과 같은 규칙을 정했습니다.

그림은 $M$ 일 동안 구매할 수 있습니다. 매일 먼저 미르코가 와서 $CM_i$ 장의 그림을 나이 $SM_i$ 이상인 그림 중에서 최대한 많이 구매하려고 합니다. 그가 원하는 그림을 구매한 후에는 슬라브코가 와서 나이 $SS_i$ 이하인 그림 중에서 최대 $CS_i$ 장의 그림을 구매하려고 합니다. 두 사람 모두 가능한 많은 그림을 사되, 상대방이 적게 구매하도록 하는 것이 목표입니다.

두 사람이 모든 $M$ 일 동안의 자신의 계획과 상대방의 계획을 미리 알고 있다면, 두 사람이 최적의 방식으로 그림을 구매할 때 미르코는 몇 장을, 슬라브코는 몇 장을 구매할 수 있을까요?

입력 첫 번째 줄에는 두 개의 자연수 $N$, $M$ ($1 ≤ N, M ≤ 200,000$)이 주어집니다. 이는 문제의 설명에서 언급된 수들입니다.

두 번째 줄에는 $N$ 개의 자연수 $S_i$ ($1 ≤ S_i ≤ 10^9$)가 주어집니다. 이는 그림의 나이를 나타내며, $1$번부터 $N$번까지 순서대로 주어집니다.

다음 $M$ 개의 줄의 $i$ 번째 줄에는 네 개의 숫자 $CM_i$, $SM_i$, $CS_i$, $SS_i$ ($1 ≤ CM_i, CS_i ≤ N$, $1 ≤ SM_i, SS_i ≤ 10^9$)가 주어집니다. 이는 문제의 설명에서 언급된 수들입니다.

출력 첫 번째 줄에 미르코가 구매할 그림의 수와 슬라브코가 구매할 그림의 수를 출력합니다.

댓글을 작성하려면 로그인해야 합니다.