16566 ์นด๋“œ๊ฒŒ์ž„

์•Œ๊ณ ๋ฆฌ์ฆ˜(์ด๋ถ„ํƒ์ƒ‰, ์ •๋ ฌ, ๋ถ„๋ฆฌ์ง‘ํ•ฉ, ์„ธ๊ทธ๋จผํŠธํŠธ๋ฆฌ?)

1. ๊ณ ๋ฅธ ์นด๋“œ๋ฅผ ๋ฒ„ํ‚ท์ •๋ ฌํ•จ(400๋งŒ๊ฐœ์ด๋ฏ€๋กœ ๋ฒ„ํ‚ท์ •๋ ฌ์ด ํ›จ์”ฌ ๋น ๋ฅด๋‹ค. sort๋Š” NlogN)
2. ๋ฒ”์œ„๋ฅผ ์ €์žฅํ•˜๋Š” set<pair<int,int>>์„ ์„ ์–ธํ•˜๊ณ  ์ฒซ ๋ฒ”์œ„๋ฅผ ๋„ฃ์Œ(0-m)
3. ์ฒ ์ˆ˜๊ฐ€ ๋ฝ‘์€ ์นด๋“œ์˜ ์ˆ˜๊ฐ€ ์ €์žฅ๋œ ๋ฒ”์œ„์˜ ๋์˜ ์ˆ˜๋ณด๋‹ค ์ž‘์„ ๋•Œ์˜ ๋ฒ”์œ„๋ฅผ ์ฐพ๊ณ , ๊ทธ ๋ฒ”์œ„์•ˆ์—์„œ uppper_bound๋กœ ํฐ์ˆ˜๋ฅผ ์ฐพ๊ณ ,
 ๊ทธ ์ฐพ์€ ๊ณต๊ฐ„์„ ์ œ์™ธํ•œ ์–‘์ชฝ์˜ ๋‘ ๋ฒ”์œ„๋ฅผ ๋‹ค์‹œ ๋ฒ”์œ„set์— ์ถ”๊ฐ€ํ•˜๊ณ , ํ˜„์žฌ ๋ฒ”์œ„๋Š” ์‚ญ์ œํ•œ๋‹ค.

 ex) ์ฒ ์ˆ˜๊ฐ€ ๋ฝ‘์€ ์ˆ˜ 5 / ๋ฒ”์œ„ : 0-3 5-7 / cards : 1 2 3 4 5 6 7 8
	1. ๋ฒ”์œ„ ์•ž์—์„œ๋ถ€ํ„ฐ ๊ฒ€์‚ฌ
		0-3 -> 3๋ฒˆ์งธ ์นด๋“œ๋Š” 4. 5๋ณด๋‹ค ์ž‘์œผ๋ฏ€๋กœ ํ†ต๊ณผ
		5-7 -> 7๋ฒˆ์งธ ์นด๋“œ๋Š” 8. 5๋ณด๋‹ค ํฌ๋ฏ€๋กœ ์Šคํƒ‘
	2. 5-7์„ ๊ธฐ์ค€์œผ๋กœ upper_bound๋ฅผ ์‹ค์‹œ : upper_bound(cards + (*iter).first, cards + (*iter).second + 1, 5);
		-> ๋‚˜์˜จ ํฌ์ธํ„ฐ๋ฅผ ์ €์žฅ
	3. 5-7์—์„œ 5๋ณด๋‹ค ํฐ ๊ฒƒ์€ 6์ด๋ฏ€๋กœ, ํฌ์ธํ„ฐ๋Š” card + 5๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ณ  ์žˆ์Œ.
	  ์ด cards + 5๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‘ ๋ฒ”์œ„๋กœ ๋ถ„๋ฆฌ์‹œํ‚จ ํ›„ ์ €์žฅ.
		-> ์ด๋•Œ ์ฒซ๋ฒˆ์งธ ์›์†Œ์ด๋ฏ€๋กœ ์™ผ์ชฝ์€ ์—†์Œ ๋”ฐ๋ผ์„œ ์˜ค๋ฅธ์ชฝ๋ฒ”์œ„๋งŒ ์ถ”๊ฐ€(6-7)
	4. ๊ธฐ์กด 5-7๋ฒ”์œ„๋Š” ์‚ญ์ œ.
	5. ์ฐพ์€ ์ˆ˜, 6์„ ๋ฆฌํ„ด.

์ฝ”๋“œ

#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#define MAX_CARD 4000000
#define MAX_DRAW 10000
 
using namespace std;
 
int cards[MAX_CARD], draw[MAX_DRAW], numOfCard, m, numOfDraw;
bool buket[MAX_CARD + 1];
set<pair<int, int>> bound;
 
void buketSort();
int findCard(int drawCard);
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> numOfCard >> m >> numOfDraw;
	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		buket[temp] = true;
	}
	for (int i = 0; i < numOfDraw; i++) {
		cin >> draw[i];
	}
	buketSort();
	bound.insert(make_pair(0, m-1));
 
	for (int i = 0; i < numOfDraw; i++)
		cout << findCard(draw[i])<< "\n";
}
 
 
void buketSort() {
	int index = 0;
	for (int i = 1; i < MAX_CARD + 1; i++)
		if (buket[i]) {
			cards[index++] = i;
		}
}
 
int findCard(int drawCard) {
 
	for (set<pair<int, int>>::iterator iter = bound.begin(); iter != bound.end(); iter++) {
		if (cards[(*iter).second] > drawCard) {
			int* temp = upper_bound(cards + (*iter).first, cards + (*iter).second + 1, drawCard);
			if(temp -cards != (*iter).first)
				bound.insert(make_pair((*iter).first, temp - cards - 1));
			if(temp - cards != (*iter).second)
				bound.insert(make_pair(temp - cards + 1, (*iter).second));
			bound.erase(iter);
			return *temp;
		}
	}
 
}