#include <bits/stdc++.h>
#define DIMN 500010
using namespace std;
int v[DIMN];
pair <int , int> cod[DIMN];
deque <int> dqr , dql;
struct segm_tree{
int l , r , lmax , rmin;
} aint[4 * DIMN];
int sol;
void build (int nod ,int st,int dr){
int mid = (st + dr)/2;
if (st == dr){
aint[nod].lmax = aint[nod].l = cod[st].first;
aint[nod].rmin = aint[nod].r = cod[st].second;
return;
}
build (2*nod,st,mid);
build (2*nod+1,mid+1,dr);
aint[nod].l = min(aint[2 * nod].l , aint[2 * nod + 1].l);
aint[nod].lmax = max(aint[2 * nod].lmax , aint[2 * nod + 1].lmax);
aint[nod].r = max(aint[2 * nod].r , aint[2 * nod + 1].r);
aint[nod].rmin = min(aint[2 * nod].rmin , aint[2 * nod + 1].rmin);
}
void query (int nod , int st , int dr , int l , int r){
int mid = (st + dr)/2;
if (l <= st && dr <= r){ /// sunt in interval bun
if (aint[nod].lmax < l || aint[nod].rmin > r){ /// tot intervalul e prost
sol += (dr - st + 1);
return;
}
if (aint[nod].l >= l && aint[nod].r <= r) /// tot intervalul e bun
return;
/// o parte din interval e buna si alta e proasta
query(2 * nod , st , mid , l , r);
query(2 * nod + 1, mid + 1 , dr , l , r);
}
else {
if (l <= mid)
query(2 * nod , st , mid , l , r);
if (mid + 1 <= r)
query(2 * nod + 1 , mid + 1 , dr , l , r);
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n, q , i , l , r;
char c;
fscanf (fin,"%d\n",&n);
for (i = 1 ; i <= n ; i++){
c=fgetc (fin);
if (c == 'C')
v[i] = 1;
else v[i] = -1;
}
for (i = n ; i ; i--){
if (v[i] == 1)
dqr.push_back(i);
}
for (i = 1 ; i <= n ; i++){
if (v[i] == 1){
cod[i] = make_pair(i , i);
dql.push_back(i);
}
else {
if (dql.empty())
l = 0;
else {
l = dql.back();
dql.pop_back();
}
while (!dqr.empty() && dqr.front() < i)
dqr.pop_front();
if (dqr.empty())
r = n + 1;
else {
r = dqr.front();
dqr.pop_front();
}
cod[i] = make_pair(l , r);
}
}
build (1 , 1 , n);
fscanf (fin,"%d",&q);
for (;q;q--){
fscanf (fin,"%d%d",&l,&r);
/// anulezi orice pct din l r care are unul sau doua capete in afara lui l r
sol = 0;
query (1 , 1 , n , l , r);
fprintf (fout,"%d\n",sol);
}
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:74:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | fscanf (fin,"%d\n",&n);
| ~~~~~~~^~~~~~~~~~~~~~~
election.cpp:119:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | fscanf (fin,"%d",&q);
| ~~~~~~~^~~~~~~~~~~~~
election.cpp:121:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | fscanf (fin,"%d%d",&l,&r);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
