BOJ 28140 | 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕!

5월 월간 향유회 C번 문제입니다.
이건 이분탐색이 정해입니다. ㄹㅇ.

구간 [l, r]이 주어질 때, 그 구간 내부에서 R과 B를 찾아야 합니다.

R을 나타내는 인덱스 a, b와 B를 나타내는 인덱스 c, d가 있을 때, $a<b<c<d$인 a, b, c, d를 구해야 합니다.

결국 구간 내부에서 가장 처음으로 등장하는 R과 가장 마지막에 등장하는 B를 찾고, 그걸 기준으로 a, b, c, d를 구해야 합니다.

$Ridx, Bidx$ 두 배열을 만들고 문자열 내부에서 R이 등장하는 인덱스와 B가 등장하는 인덱스를 기록합니다.

그 후, 쿼리가 들어오면 [l, r]에서 l을 기준으로 R을 찾고, r을 기준으로 B를 찾은 뒤 그 인덱스를 기반으로 a, b, c, d를 모두 찾고 $a<b<c<d$에 부합하면 출력합니다.

만약 $b \geq c$라면 -1입니다.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'


int main(){
	FASTIO;
	int N, Q; cin >> N >> Q;
	string S; cin >> S;
	
	vector<int> Ridx;
	vector<int> Bidx;
	
	for (int i = 0; i < S.size(); i++){
		if (S[i] == 'R') Ridx.push_back(i);
		if (S[i] == 'B') Bidx.push_back(i);
	}
	
	sort(Ridx.begin(), Ridx.end());
    sort(Bidx.begin(), Bidx.end());
	
	for (int i = 0; i < Q; i++){
		int a, b; cin >> a >> b;
		int r1 = lower_bound(Ridx.begin(), Ridx.end(), a) - Ridx.begin();
		int r2 = upper_bound(Ridx.begin(), Ridx.end(), b) - Ridx.begin();
		int b1 = lower_bound(Bidx.begin(), Bidx.end(), a) - Bidx.begin();
		int b2 = upper_bound(Bidx.begin(), Bidx.end(), b) - Bidx.begin();

		r2--;
		b2--;
		
		if (r2-r1+1 < 2 || b2-b1+1 < 2){
			cout << -1 << endl;
			continue;
		}
		
		if (Ridx[r1+1] >= Bidx[b2-1]){
			cout << -1 << endl;
			continue;
		}
		
		cout << Ridx[r1] << ' ' << Ridx[r1+1] << ' ' << Bidx[b2-1] << ' ' << Bidx[b2] << endl;
	}
}