AcWing 4888. 领导者
原题链接
简单
作者:
懒惰的蚩蚩
,
2024-10-13 22:03:23
,
所有人可见
,
阅读 7
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15;
// typedef pair<int, int> PII;
vector<int> lead_G, lead_H, ans_G, ans_H;
int n;
int a[N];
string str;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> str;
int left_G = N, rigth_G = 0, left_H = N, rigth_H = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(str[i - 1] == 'G') {
// cnt_G = max(i, cnt_G);
left_G = min(i, left_G);
rigth_G = max(i, rigth_G);
}
else if(str[i - 1] == 'H') {
// cnt_H = max(i, cnt_H);
left_H = min(i, left_H);
rigth_H = max(i, rigth_G);
}
}
// cout << left_G << " " << rigth_G << endl;
// cout << left_H << " " << rigth_H << endl;
for(int i = 1; i <= n; i++) {
if(str[i - 1] == 'G' && i <= left_G && a[i] >= rigth_G) {
lead_G.push_back(i);
ans_G.push_back(i);
}
if(str[i - 1] == 'H' && i <= left_H && a[i] >= rigth_H) {
lead_H.push_back(i);
ans_H.push_back(i);
}
}
// if(lead_G.size() > 0) sort(lead_G.begin(), lead_G.end());
// if(lead_H.size() > 0) sort(lead_H.begin(), lead_H.end());
// for(auto g : lead_G) cout << g << " ";
// cout << endl;
// for(auto h : lead_H) cout << h << " ";
// cout << endl;
// int ans = 0;
for(int i = 1; i <= n; i++) {
if(lead_G.size() > 0 && str[i - 1] == 'H') {
for(auto g : lead_G) {
if(i <= g && g <= a[i]) {
ans_H.push_back(i);
// ans++;
// cout << i << endl;
}
}
}
if(lead_H.size() > 0 && str[i - 1] == 'G') {
for(auto h : lead_H) {
if(i <= h && h <= a[i]) {
ans_G.push_back(i);
// ans++;
// cout << i << endl;
}
}
}
}
sort(ans_G.begin(), ans_G.end());
ans_G.erase(unique(ans_G.begin(), ans_G.end()), ans_G.end());
sort(ans_H.begin(), ans_H.end());
ans_H.erase(unique(ans_H.begin(), ans_H.end()), ans_H.end());
// cout << ans << endl;
int ans = ans_G.size() * ans_H.size();
cout << ans << endl;
return 0;
}