백준 19580 (C++) 마스크가 필요해

최초 업로드: 2025-07-20 01:09:53

최근 수정 시간: 2025-07-25 08:43:28

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 마스크가 필요해

[문제 링크](https://www.acmicpc.net/problem/19580)

## 문제 설명

코로나19가 발생하고 나서 마스크의 필요성이 증가하기 시작했다. 마스크가 없으면 생활을 하는데 어려움이 있기 때문에 마스크를 항상 구비하고 있어야 한다.

마스크의 수요가 증가함에 따라 일정했던 마스크의 가격이 상점마다 달라지게 되었다. 마스크의 가격이 제각각이기 때문에 A도시의 시민들이 전부 마스크를 갖기가 어려워지기 시작했다. A도시의 공무원인 당신은 이 사태를 해결하기 위해서 상점의 주인들에게 마스크의 가격을 일정하게 해달라고 했지만, 상점 주인들은 당연히 무시했다.

상점 주인들을 설득시키는 것은 어렵다고 생각해서 당신은 최대한 많은 시민들이 마스크를 가질 수 있게 하는 것으로 계획을 변경했다. 당신은 A도시의 각 시민이 마스크에 소비할 수 있는 금액의 범위와 A도시의 상점에서 팔고 있는 마스크의 가격 및 개수를 알아냈다. 각 시민은 최대 1개의 마스크만 살 수 있다. 이 정보를 바탕으로 최대한 많은 시민들이 마스크를 얻을 수 있게 하자.

## 입력

첫 번째 줄에는 A도시의 시민 수인 N과 A도시의 상점 수인 M이 주어진다. (1 ≤ N, M ≤ 500,000)

두 번째 줄부터 N + 1번째 줄까지는 A도시의 각 시민이 마스크에 소비할 수 있는 돈의 범위인 Li, Ri가 주어진다. 즉 i번째 A도시 시민이 살 수 있는 마스크의 가격은 Li 이상 Ri 이하이다. (1 ≤ Li ≤ Ri ≤ 1018)

N + 2번째 줄부터 N + M + 1번째 줄까지는 A도시의 각 상점이 판매하고 있는 마스크의 가격인 Pj와 마스크의 개수인 Xj가 주어진다. (1 ≤ Pj ≤ 1018, 1 ≤ Xj ≤ 1,000)

모든 Li, Ri, Pj, Xj는 정수이다.

## 출력

가능한 한 많은 시민이 마스크를 샀을 때, 마스크를 산 시민의 수를 출력한다.

## 풀이
#### 모든 선택할 수 있는 시민 중 가장 R이 작은 주민을 선택하면 된다. 즉, L이 상점 왼쪽에 있는 모든 시민들을 우선순위 큐에 넣고 R이 가장 작은 시민부터 할당해주면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct citizen {
 ll s, e;
 bool operator<(const citizen c) const {
 if(s!=c.s) return s < c.s;
 return e < c.e;
 }
};

struct citizenPQ {
 ll s, e;
 citizenPQ(citizen c) {
 s = c.s;
 e = c.e;
 }
 bool operator<(const citizenPQ c) const {
 if(e!=c.e) return e > c.e;
 return s > c.s;
 }
};

struct store {
 ll p, x;
 bool operator<(const store s) const {
 return p < s.p;
 }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 vector<citizen> citizens(n);
 for(int i=0;i<n;i++) cin >> citizens[i].s >> citizens[i].e;
 sort(citizens.begin(), citizens.end());

vector<store> stores(m);
 for(int i=0;i<m;i++) cin >> stores[i].p >> stores[i].x;
 sort(stores.begin(), stores.end());

int cnt=0, citizenIdx=0;
 priority_queue<citizenPQ> pq;
 for(store s : stores) {
 while(citizenIdx<n && citizens[citizenIdx].s<=s.p) {
 pq.push(citizens[citizenIdx++]);
 }
 while(s.x && !pq.empty()) {
 auto cur = pq.top(); pq.pop();
 if(cur.s<=s.p && s.p<=cur.e) {
 cnt++;
 s.x--;
 }
 }
 }
 cout << cnt;
}
```