#include <bits/stdc++.h>
using namespace std;
struct segment_tree{
vector<int> st, stadd;
int maxn = 0;
void init(int n){
maxn = n;
while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
st.assign(2*maxn, 0);
stadd.assign(2*maxn, 0);
return;
}
void pont_update(int x, int l, int r){
if(l+1 == r){
st[x] += stadd[x];
stadd[x] = 0;
return;
}
st[x] = min(st[2*x+1], st[2*x+2]) + stadd[x];
return;
}
void propagate(int x, int l, int r){
if(l+1 == r){
pont_update(x, l, r);
return;
}
int m = (l+r)/2;
stadd[2*x+1] += stadd[x];
stadd[2*x+2] += stadd[x];
stadd[x] = 0;
pont_update(2*x+1, l, m);
pont_update(2*x+2, m, r);
pont_update(x, l, r);
return;
}
void add(int L, int R, int c, int x, int l, int r){
propagate(x, l, r);
if(r <= L || R <= l)
return;
if(L <= l && r <= R){
stadd[x] += c;
pont_update(x, l, r);
return;
}
int m = (l+r)/2;
add(L, R, c, 2*x+1, l, m);
add(L, R, c, 2*x+2, m, r);
return;
}
void add(int l, int r, int c){
add(l, r, c, 0, 0, maxn);
return;
}
int keres(int L, int c, int x, int l, int r, bool f){
propagate(x, l, r);
if(l+1 == r)
return (L <= l && st[x] == c ? l : -1);
int m = (l+r)/2;
if(f){
if(st[2*x+1] <= c)
return keres(L, c, 2*x+1, l, m, true);
return keres(L, c, 2*x+2, m, r, true);
}
if(m <= L)
return keres(L, c, 2*x+2, m, r, false);
int ret = -1;
if(st[2*x+1] <= c)
ret = keres(L, c, 2*x+1, l, m, false);
if(ret == -1 || st[2*x+1] > c)
return keres(L, c, 2*x+2, m, r, true);
return ret;
}
int keres(int L, int c){
return keres(L, c, 0, 0, maxn, false);
}
int ertek(int L, int R, int x, int l, int r){
propagate(x, l, r);
if(r <= L || R <= l)
return (int)1e9;
if(L <= l && r <= R)
return st[x];
int m = (l+r)/2;
return min(ertek(L, R, 2*x+1, l, m), ertek(L, R, 2*x+2, m, r));
}
int ertek(int l, int r){
return ertek(l, r, 0, 0, maxn);
}
int elem(int ind, int x, int l, int r){
propagate(x, l, r);
if(l+1 == r)
return st[x];
int m = (l+r)/2;
if(ind < m)
return elem(ind, 2*x+1, l, m);
return elem(ind, 2*x+2, m, r);
}
int elem(int x){
return elem(x, 0, 0, maxn);
}
};
struct segment_tree2{
vector<int> st;
int maxn = 0;
void init(int n){
maxn = n;
while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
st.assign(2*maxn, 0);
return;
}
void update(int x, int c){
st[x+maxn] = c;
for(int i = (x+maxn)>>1; i > 0; i >>= 1)
st[i] = st[2*i] + st[2*i+1];
return;
}
int ertek(int L, int R, int x, int l, int r){
if(r <= L || R <= l)
return 0;
if(L <= l && r <= R)
return st[x];
return ertek(L, R, 2*x, l, (l+r)/2) + ertek(L, R, 2*x+1, (l+r)/2, r);
}
int ertek(int l, int r){
return ertek(l, r, 1, 0, maxn);
}
};
int main()
{
cin.sync_with_stdio(false);
cin.tie(0);
int n, q;
string s;
cin>>n;
cin>>s;
cin>>q;
vector<vector<pair<int, int>>> v(n);
for(int i = 0; i < q; i++){
int l, r;
cin>>l>>r;
v[l-1].push_back(make_pair(r-1, i));
}
vector<int> kov(n);
iota(kov.begin(), kov.end(), 1);
vector<int> ki(q);
segment_tree st, st2;
segment_tree2 st3;
st.init(n+1);
st2.init(n+1);
st3.init(n+1);
vector<bool> volt(n, false);
for(int i = 0; i < n; i++){
if(s[i] == 'C')
volt[i] = true;
else
st3.update(i, 1);
}
int x = n-1, last = n-1;
for(int i = n-1; i >= 0; i--){
if(s[i] == 'C'){
while(x < n && volt[x])
x = kov[x];
if(x < n){
if(last != x)
kov[last] = x;
volt[x] = true;
st3.update(x, 0);
int temp = st.ertek(i, x);
//cout<<"min ertek: "<<temp<<"\n";
int ind = st.keres(x, temp-1);
//cout<<"min ind: "<<ind<<"\n";
if(ind == -1) ind = n+1;
st2.add(x, ind-1, 1);
st.add(0, x+1, -1);
}
st.add(0, i+1, 1);
} else
x = last = i;
for(pair<int, int> temp : v[i])
ki[temp.second] = st2.elem(temp.first) + st3.ertek(i, temp.first+1);
/*cout<<"sor: ";
for(int j = 0; j < n; j++)
cout<<st.elem(j)<<" ";
cout<<"\n";
cout<<"sor2: ";
for(int j = 0; j < n; j++)
cout<<st2.elem(j)<<" ";
cout<<"\n";
cout<<"st3: "<<st3.ertek(i, n)<<"\n";*/
}
for(int x : ki)
cout<<x<<"\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
