AcWing 4888. 领导者
原题链接
简单
作者:
懒惰的蚩蚩
,
2024-10-13 22:03:23
,
所有人可见
,
阅读 35
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15;
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') {
left_G = min(i, left_G);
rigth_G = max(i, rigth_G);
}
else if(str[i - 1] == 'H') {
left_H = min(i, left_H);
rigth_H = max(i, rigth_G);
}
}
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);
}
}
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);
}
}
}
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);
}
}
}
}
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());
int ans = ans_G.size() * ans_H.size();
cout << ans << endl;
return 0;
}