| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 467836 | nickmet2004 | Election (BOI18_election) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n , a[N];
string s;
struct Node{
int L , R , cnt , ans;
Node operator+(Node y){
Node ret;
ret.cnt = cnt + y.cnt;
ret.L = max(L + cnt + y.L);
ret.R = max(y.R , y.cnt + R);
ret.ans = max({ans + y.cnt , y.ans + cnt , L + y.R});
return ret;
}
}T[4*N];
void B(int l = 0 , int r = n - 1 , int pos = 0){
if(l == r){
if(a[l] == 1) T[pos] = {1 , 1, 1, 1};
else T[pos] = {0 , 0 , -1 , 0};
return;
}
int mid = (l + r) >> 1;
B(l , mid , pos * 2 + 1);
B(mid + 1 ,r , pos * 2 + 2);
T[pos] = T[pos *2 + 1] + T[pos *2 + 2];
}
Node get(int L , int R , int l =0 , int r = n - 1 , int pos = 0){
if(r <L || R < l) return {0 , 0 , 0 , 0};
if(L <= l && r <= R) return T[pos];
int mid = (l + r) >> 1;
return get(L , R , l , mid , pos * 2 + 1) + get(L , R , mid + 1 , r , pos * 2 + 2);
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> s;
memset(a , -1 , sizeof(a));
for(int i = 0;i < n; ++i){
if(s[i] == 'T')a[i] = 1;
}
B();
int q;
cin >> q;
while(q--){
int a , b;
cin >> a >> b;
--a; --b;
cout << get(a , b).ans << endl;
}
}