# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;
vector< pair<int, int> > pref[500001], suff[500001];
int ans[500001];
int N;
string S;
int seg[2000001];
void build(int lf, int rg, int nd) {
seg[nd] = 0;
if(lf == rg) return;
int mid = (lf + rg)/2;
build(lf, mid, 2*nd+1);
build(mid+1, rg, 2*nd+2);
}
void upd(int lf, int rg, int nd, int clf, int crg) {
if(clf > rg || lf > crg) return;
if(clf <= lf && rg <= crg) seg[nd]++;
else {
int mid = (lf + rg) / 2;
upd(lf, mid, 2*nd+1, clf, crg);
upd(mid+1, rg, 2*nd+2, clf, crg);
}
}
int qry(int lf, int rg, int nd, int pos) {
if(lf == rg) return seg[nd];
else {
int mid = (lf + rg) / 2;
seg[2*nd+1] += seg[nd];
seg[2*nd+2] += seg[nd];
seg[nd] = 0;
if(pos <= mid) return qry(lf, mid, 2*nd+1, pos);
else return qry(mid+1, rg, 2*nd+2, pos);
}
}
void calc() {
vector< pair<int, int> > L, V;
L.clear();
V.clear();
// cout<<"before"<<endl;
build(0, N-1, 0);
for(int i=0;i<N;i++) {
// cout<<i<<endl;
if(V.size() == 0) V.push_back(make_pair(i, i));
else V.back().se++;
if(S[i] == 'C') {
if(V.size() == 0) {
L.back().se++;
} else {
L.push_back(V.back());
L.push_back(make_pair(-1, 1));
V.clear();
}
} else {
if(V.size() == 1) upd(0, N-1, 0, V.back().fi, V.back().se);
// if(V.size() > 0) cout<<i<<" "<<V.back().fi<<" "<<V.back().se<<endl;
if(L.size() && L.back().se == 1) {
L.pop_back();
if(V.size() == 0) V.push_back(L.back());
else V.back().fi = L.back().fi;
L.pop_back();
} else if(L.size()) L.back().se--;
}
for(int k=0;k<pref[i].size();k++) {
// cout<<"qry : "<<pref[i][k].se<<" "<<pref[i][k].fi<<endl;
ans[pref[i][k].se] = max(ans[pref[i][k].se], qry(0, N-1, 0, pref[i][k].fi));
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>N;
cin>>S;
int Q;
cin>>Q;
for(int tc = 1;tc<=Q;tc++) {
int a, b;
cin>>a>>b;
a--;
b--;
pref[b].push_back(make_pair(a, tc));
suff[a].push_back(make_pair(b, tc));
}
// calculate prefnya dulu
calc();
// cout<<"one"<<endl;
string T = "";
for(int i=N-1;i>=0;i--) T += S[i];
S = T;
for(int i=0;i<N;i++) pref[i].clear();
for(int i=N-1;i>=0;i--) {
for(int k=0;k<suff[i].size();k++) {
pref[N - i - 1].push_back(make_pair(N - suff[i][k].fi - 1, suff[i][k].se));
}
}
calc();
for(int i=1;i<=Q;i++) printf("%d\n", ans[i]);
return 0;
}
Compilation message
election.cpp: In function 'void calc()':
election.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int k=0;k<pref[i].size();k++) {
| ~^~~~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:110:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int k=0;k<suff[i].size();k++) {
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
