Submission #1007159

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MAXN = 220000;

int n;
int b[MAXN];
int a[MAXN];
char s[MAXN];
set<pair<int, int> > ss0;
set<pair<int, int> > ss1;
set<pair<int, int> > ms0;
set<pair<int, int> > ms1;

int check(int x) {
	for (int i = 0; i < n; ++i)
		a[i] = (b[i] >= x ? 1 : 0);
	int c0 = 0;
	int c1 = 0;
	ss0.clear();
	ss1.clear();
	ms0.clear();
	ms1.clear();
	int l = 0;
	for (int i = 0; i < n; ++i) {
		if (i == n - 1 || a[i] != a[i + 1]) {
			if (a[i] == 0) {
				ss0.insert(make_pair(i - l + 1, l));
				ms0.insert(make_pair(l, i - l + 1));
			}
			else {
				ss1.insert(make_pair(i - l + 1, l));
				ms1.insert(make_pair(l, i - l + 1));
			}
			l = i + 1;
		}
	}
	for (int i = 0; i < n - 1; ++i) {
		if (s[i] == 'M') {
			++c1;
			while (!ss0.empty() && ss0.begin()->first + c0 - c1 <= 0) {
				int len = ss0.begin()->first;
				int p = ss0.begin()->second;
				ss0.erase(make_pair(len, p));
				ms0.erase(make_pair(p, len));
				auto itr = ms1.lower_bound(make_pair(p, 0));
				if (itr == ms1.end() || itr == ms1.begin())
					continue;
				auto itl = itr;
				--itl;
				pair<int, int> pl = *itl;
				pair<int, int> pr = *itr;
				pair<int, int> nw = make_pair(pl.first, (pl.second - c0 + c1) + (pr.second - c0 + c1) - c1 + c0);
				ms1.erase(itl);
				ms1.erase(itr);
				ss1.erase(make_pair(pl.second, pl.first));
				ss1.erase(make_pair(pr.second, pr.first));
				ms1.insert(nw);
				ss1.insert(make_pair(nw.second, nw.first));
			}
		}
		else {
			++c0;
			while (!ss1.empty() && ss1.begin()->first + c1 - c0 <= 0) {
				int len = ss1.begin()->first;
				int p = ss1.begin()->second;
				ss1.erase(make_pair(len, p));
				ms1.erase(make_pair(p, len));
				auto itr = ms0.lower_bound(make_pair(p, 0));
				if (itr == ms0.end() || itr == ms0.begin())
					continue;
				auto itl = itr;
				--itl;
				pair<int, int> pl = *itl;
				pair<int, int> pr = *itr;
				pair<int, int> nw = make_pair(pl.first, (pl.second - c1 + c0) + (pr.second - c1 + c0) - c0 + c1);
				ms0.erase(itl);
				ms0.erase(itr);
				ss0.erase(make_pair(pl.second, pl.first));
				ss0.erase(make_pair(pr.second, pr.first));
				ms0.insert(nw);
				ss0.insert(make_pair(nw.second, nw.first));
			}
		}
	}
	for (auto it: ms1) {
		int p = it.first;
		int l = it.second;
		p -= c1;
		l += c1 - c0;
		if (p <= 0 && p + l > 0)
			return 1;
	}
	return 0;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", b + i);
	scanf(" %s", s);
	int lb = 0;
	int rb = 120000;
	while (rb - lb > 1) {
		int mid = (lb + rb) >> 1;
		if (check(mid))
			lb = mid;
		else
			rb = mid;
	}
	cout << lb << "\n";
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:117:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:119:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b + i);
                     ^
./Main.cpp:120:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", s);
                 ^

Judge Result