#include<bits/stdc++.h>
using namespace std;
#define brokenheart "TEST"
#define pb push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
int n , q;
string s;
namespace IT
{
const int cant = 1e9;
struct TNode
{
int dep , suf;
TNode(int _x , int _y) : dep(_x) , suf (_y) {};
TNode (char x){dep = suf = (x == 'C' ? 1 : -1);}
TNode(){};
TNode operator + (const TNode & other) const &
{
if(suf == cant)return other;
if(other.suf == cant)return (*this);
TNode res;
res.dep = dep + other.dep;
res.suf = min(other.suf,other.dep+suf);
return res;
}
}a[maxn * 4];
TNode query(int x , int l , int r , int L , int R)
{
if(l > R || L > r)return TNode(cant,cant);
if(L <= l && r <= R)return a[x];
int mid = l + r >> 1;
return query(x * 2 , l , mid , L , R) + query(x * 2 + 1 , mid + 1 , r , L , R);
}
TNode query(int l , int h){return query(1,1,n,l,h);};
void update(int x , int l , int r , int pos , int val)
{
if(l == r)
{
a[x] = TNode(val,val);
return;
}
int mid = l + r >> 1;
if(mid >= pos)update(x * 2 , l , mid , pos , val);
else update(x * 2 + 1 , mid + 1 , r , pos , val);
a[x] = a[x * 2] + a[x * 2 + 1];
}
void update(int pos , int val){update(1,1,n,pos,val);}
void build(int x , int l , int h)
{
if(l == h)
{
a[x] = TNode(s[l]);
return;
}
int mid = l + h >> 1;
build(x * 2 , l , mid);
build(x * 2 + 1 , mid + 1 , h);
a[x] = a[x * 2] + a[x * 2 + 1];
}
void build()
{
s = " " + s;
build(1 , 1 , n);
}
}
struct TQuery
{
int h , id;
};
int res[maxn];
vector<TQuery> Vq[maxn];
vector<int> del;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(brokenheart".INP","r"))
freopen(brokenheart".INP", "r",stdin) ,
freopen(brokenheart".OUT", "w",stdout);
cin >> n >> s;
IT::build();
cin >> q;
for(int i = 1 ; i <= q ; ++i)
{
int l , h;cin >> l >> h;
Vq[l].pb({h , i});
}
for(int i = n ; i >= 1 ; --i)
{
if(s[i] == 'T')
{
IT::update(i,0);
del.push_back(i);
}
else
{
if(!del.empty())
{
IT::update(del.back(),-1);
del.pop_back();
}
}
for(auto q : Vq[i])
{
res[q.id] = (upper_bound(del.begin(),del.end(),q.h) - del.begin())
- min(IT::query(i,q.h).suf,0);
// cout << q.id << " " << IT::query(i,q.h).suf << '\n';
}
}
for(int i = 1 ; i <= q ; ++i)cout << res[i] << '\n';
}
Compilation message
election.cpp: In function 'IT::TNode IT::query(int, int, int, int, int)':
election.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
election.cpp: In function 'void IT::update(int, int, int, int, int)':
election.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
election.cpp: In function 'void IT::build(int, int, int)':
election.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + h >> 1;
~~^~~
election.cpp: In function 'int main()':
election.cpp:93:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(brokenheart".INP", "r",stdin) ,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
freopen(brokenheart".OUT", "w",stdout);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:93:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
