#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991
const int maxn = 200001;
const int sq = sqrt(maxn) + 1;
// {query index, left, right}
array<int,3> Q[maxn];
int ans[maxn], pl[maxn], pr[maxn];
bitset<maxn> active;
bool cmp (array<int,3> a, array<int,3> b) {
a[0] /= sq;
b[0] /= sq;
return a < b;
}
signed main () {
cin.tie(0)->sync_with_stdio(0);
int n, q;
string s;
cin >> n >> s >> q;
for (int i = 0 ; i < q ; i++) {
int l, r;
cin >> l >> r;
l--,r--;
Q[i] = {l, r, i};
}
sort(Q, Q + q, cmp);
set<int> TL, TR, CL, CR;
int CNT = 0;
// CL: C empty from the Left
// CR: C empty from the right
// TL: T that needs Left
memset(pl, -1, sizeof pl);
memset(pr, -1, sizeof pr);
auto activate = [&](int x) {
if (!active[x]) active[x] = 1, CNT++;
};
auto deactivate = [&](int x) {
if (!TL.count(x) and !TR.count(x)) active[x] = 0, CNT--;
};
int l = 0, r = -1;
for (int i = 0 ; i < q ; i++) {
auto [nl, nr, id] = Q[i];
while (r < nr) {
r++;
if (s[r] == 'T') {
if (CR.size()) {
pl[r] = *--CR.end();
CR.erase(--CR.end());
} else TL.insert(r), activate(r);
TR.insert(r), activate(r);
} else {
if (TR.size()) {
pl[r] = *TR.begin();
TR.erase(TR.begin());
deactivate(pl[r]);
} else {
CL.insert(r);
}
CR.insert(r);
}
}
while (l > nl) {
l--;
if (s[l] == 'T') {
if (CL.size()) {
pr[l] = *CL.begin();
CL.erase(CL.begin());
} else TR.insert(l), activate(l);
TL.insert(l), activate(l);
} else {
if (TL.size()) {
pr[r] = *--TL.end();
TL.erase(--TL.end());
deactivate(pr[r]);
} else {
CR.insert(l);
}
CL.insert(l);
}
}
while (r > nr) {
if (s[r] == 'T') {
if (pl[r] != -1) {
auto it = TL.lower_bound(pl[r]);
if (it != TL.end()) {
pl[*it] = pl[r];
pr[pl[r]] = *it;
TL.erase(it);
deactivate(pr[pl[r]]);
}
pl[r] = -1;
} else TL.erase(r), deactivate(r);
TR.erase(r), deactivate(r);
} else {
if (pl[r] != -1) {
auto it = CL.lower_bound(pl[r]);
if (it != CL.end()) {
pl[*it] = pl[r];
pr[pl[r]] = *it;
CL.erase(it);
}
pl[r] = -1;
} else CL.erase(r);
CR.erase(r);
}
r--;
}
while (l < nl) {
if (s[l] == 'T') {
if (pr[l] != -1) {
auto it = TR.upper_bound(pr[l]);
if (it != TR.begin()) {it--;
pr[*it] = pr[l];
pl[pr[l]] = *it;
TR.erase(it);
deactivate(pl[pr[l]]);
}
pr[l] = -1;
} else TR.erase(l), deactivate(l);
TL.erase(l), deactivate(l);
} else {
if (pr[l] != -1) {
auto it = CR.upper_bound(pr[l]);
if (it != CR.begin()) {it--;
pr[*it] = pr[l];
pl[pr[l]] = *it;
CR.erase(it);
}
pr[l] = -1;
} else CR.erase(l);
CL.erase(l);
}
l++;
}
ans[id] = CNT;
}
for (int i = 0 ; i < q ; i++) cout << ans[i] << endl;
}
Compilation message
election.cpp:17:1: warning: multi-line comment [-Wcomment]
17 | //\
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
