#include<bits/stdc++.h>
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main(){
int n;
cin >>n;
vector<char> v(n);
vector<int> t;
vector<int> c;
int tt=0;
int tc=0;
bool proslit = false;
bool proslic = false;
cin >> v[0];
if(v[0] == 'T'){
proslit=true;
tt++;
}
else{
proslic=true;
tc++;
}
bool prvitony = proslit;
for(int i = 1; i < n; i++){
cin>>v[i];
if(v[i]=='T'){
if(proslit == true){
tt++;
}
else{
if(tt >0)t.push_back(tt);
tt=1;
}
proslic=false;
proslit=true;
}
else{
if(proslic == true){
tc++;
}
else{
if(tc>0)c.push_back(tc);
tc=1;
}
proslit=false;
proslic=true;
}
}
if(tc>0)c.push_back(tc);
if(tt>0)t.push_back(tt);
vector<pair<int,bool>> g;
if(prvitony){
if(t.size()>0)g.push_back(make_pair(t[0],true));
if(c.size()>0)g.push_back(make_pair(c[0]+g[0].first,false));
for(int i = 1; i < c.size();i++){
g.push_back(make_pair(t[i]+g[2*i-1].first,true));
g.push_back(make_pair(c[i]+g[2*i].first,false));
}
if(t.size()>c.size()&& t.size()>1)g.push_back(make_pair(t[t.size()-1]+g[g.size()-1].first,true));
}
else{
if(c.size()>0)g.push_back(make_pair(c[0],false));
if(t.size()>0)g.push_back(make_pair(t[0]+g[0].first,true));
for(int i = 1; i < t.size();i++){
g.push_back(make_pair(c[i]+g[2*i-1].first,false));
g.push_back(make_pair(t[i]+g[2*i].first,true));
}
if(c.size()>t.size()&& c.size()>1)g.push_back(make_pair(c[c.size()-1]+g[g.size()-1].first,false));
}
int q;
cin >> q;
int l,r;
while(q--){
cin >> l >> r;
vector<int>kill;
int i = 0;
while(g[i].first<l){
i++;
if(i==g.size())break;
}
int j = 0;
while(g[j].first<r){
j++;
if(j==g.size())break;
}
if(i == j){
if(g[i].second == true)kill.push_back(r-l+1);
}
else{
int levi1 = g[i].first-l+1;
bool levi2 = g[i].second;
int desni1=r-g[j-1].first;
bool desni2=g[j].second;
bool toni=levi2;
int capwins = 0;
if(toni){
kill.push_back(levi1);
}
else capwins+=levi1;
toni=!toni;
for(int k = i+1; k < j;k++){
if(toni){
if(capwins>=g[k].first-g[k-1].first){
capwins-=g[k].first-g[k-1].first;
kill.push_back(0);
}
else{
kill.push_back(g[k].first-g[k-1].first-capwins);
capwins=0;
}
toni=!toni;
}
else{
capwins+=g[k].first-g[k-1].first;
toni=!toni;
}
}
if(toni){
if(desni1>capwins){
kill.push_back(desni1-capwins);
capwins=0;
}
else kill.push_back(0);
}
int u = 1;
capwins = 0;
if(toni){
kill[kill.size()-u]=max(kill[kill.size()-u],desni1);
u++;
}
else capwins+=desni1;
toni=!toni;
for(int k = j-1; k > i;k--){
if(toni){
if(capwins>=g[k].first-g[k-1].first){
capwins-=g[k].first-g[k-1].first;
kill[kill.size()-u]=max(kill[kill.size()-u],0);
u++;
}
else{
kill[kill.size()-u]=max(kill[kill.size()-u],g[k].first-g[k-1].first-capwins);
capwins=0;
u++;
}
toni=!toni;
}
else{
capwins+=g[k].first-g[k-1].first;
toni=!toni;
}
}
if(toni){
kill[kill.size()-u]=max(kill[kill.size()]-u,levi1);
kill.push_back(levi1);
}
}
int h = 0;
for(int i = 0; i < kill.size();i++)h+=kill[i];
cout << h << endl;
}
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 1; i < c.size();i++){
| ~~^~~~~~~~~~
election.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 1; i < t.size();i++){
| ~~^~~~~~~~~~
election.cpp:86:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | if(i==g.size())break;
| ~^~~~~~~~~~
election.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(j==g.size())break;
| ~^~~~~~~~~~
election.cpp:100:10: warning: unused variable 'desni2' [-Wunused-variable]
100 | bool desni2=g[j].second;
| ^~~~~~
election.cpp:172:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0; i < kill.size();i++)h+=kill[i];
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
