이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define N 500005
struct node{
int rm, lm, sum, ans;
node(){
rm = lm = sum = ans = 0;
}
node operator + (node o){
node rt;
rt.sum = sum + o.sum;
rt.lm = max(lm, sum + o.lm);
rt.rm = max(o.rm, o.sum + rm);
rt.ans = max({lm + o.rm, ans + o.sum, sum + o.ans});
return rt;
}
};
struct segtree
{
int n;
vector<node> bit;
segtree(int siz){
n = siz;
bit.resize(4 * siz + 1);
}
void ud(int id, int l, int r, int pos, int typ){
if (l > pos || r < pos) return;
if (l == r){
if (typ == 1) bit[id].rm = bit[id].lm = bit[id].sum = bit[id].ans = 1;
else bit[id].rm = 0, bit[id].lm = 0, bit[id].sum = -1, bit[id].ans = 0;
return;
}
int mid = (l + r) >> 1;
ud(id * 2, l, mid, pos, typ);
ud(id * 2 + 1, mid + 1, r, pos, typ);
bit[id] = bit[id * 2] + bit[id * 2 + 1];
}
node nll;
node get(int id, int l, int r, int u, int v){
if (l > v || r < u) return nll;
if (l >= u && r <= v) return bit[id];
int mid = (l + r) >> 1;
node t = get(id * 2, l, mid, u, v);
node tt = get(id * 2 + 1, mid + 1, r, u, v);
return (t + tt);
}
void insert(int pos, int typ){
ud(1, 1, n, pos, typ);
}
int get(int l, int r){
return get(1, 1, n, l, r).ans;
}
};
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int n;
string s;
cin >> n;
cin >> s;
segtree s1(n);
s = " " + s;
for (int i = 1; i <= n; i++){
if (s[i] == 'C'){
s1.insert(i, -1);
}
else s1.insert(i, 1);
}
int q;
cin >> q;
while (q--){
int l, r;
cin >> l >> r;
cout << s1.get(l, r) << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |