#include <bits/stdc++.h>
#define DIMN 500010
using namespace std;
int vi[DIMN] , sp[DIMN] , tt[DIMN] , next_c[DIMN];
map <int , int> mp;
pair <int , int> rmq[20][DIMN];
int srmq[20][DIMN];
int last[20][DIMN];
vector <int> v[DIMN];
int aint[4 * DIMN];
int sol;
char buff[10000000];
int pos = 0;
int getnr(){
int nr = 0;
while ('0' > buff[pos] || buff[pos] > '9')
pos++;
while ('0' <= buff[pos] && buff[pos] <= '9'){
nr = nr * 10 + buff[pos] - '0';
pos++;
}
return nr;
}
void build (int nod ,int st,int dr){
int mid = (st + dr)/2;
if (st == dr){
aint[nod] = min(0 , vi[st]);
return;
}
build (2*nod,st,mid);
build (2*nod+1,mid+1,dr);
aint[nod] = min(aint[2 * nod + 1] , sp[dr] - sp[mid] + aint[2 * nod]);
}
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
sol = min(sol , aint[nod] + sp[r] - sp[dr]);
}
else {
if (mid + 1 <= r)
query(2 * nod + 1 , mid + 1 , dr , l , r);
if (l <= mid)
query(2 * nod , st , mid , l , r);
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
//FILE *ans = fopen ("idk.in","r");
int n, q , i , l , r , nod , j , vecin , maxi , fth , inc = 0;
char c;
fscanf (fin,"%d\n",&n);
for (i = 1 ; i <= n ; i++){
c=fgetc(fin);
if (c == 'C')
vi[i] = 1;
else vi[i] = -1;
sp[i] = vi[i] + sp[i - 1];
}
next_c[n + 1] = n + 1;
for (i = n ; i ; i--){
if (vi[i] == 1)
next_c[i] = i;
else next_c[i] = next_c[i + 1];
}
for (i = n ; i ; i--){
/// sp[j] - sp[i - 1] = -1
/// sp[j] = -1 + sp[i - 1]
if (vi[i] == -1){
v[i + 1].push_back(i);
tt[i] = i + 1;
}
else {
if (mp[sp[i - 1] - 1] != 0){
v[mp[sp[i - 1] - 1]].push_back(i); /// intervalul i...chestie are suma -1
tt[i] = mp[sp[i - 1] - 1];
}
else {
v[n + 1].push_back(i); /// n + 1 = nod fictiv radacina
tt[i] = n + 1;
}
}
mp[sp[i]] = i;
}
build (1 , 1 , n);
/// vezi ce valoare dai muchiilor
for (nod = 1 ; nod <= n + 1 ; nod++){ /// nod este tatal
for (j = 0 ; j < v[nod].size() ; j++){
vecin = v[nod][j];
//printf ("%d %d " , vecin , nod);
if (nod - vecin > 1 || (nod - vecin == 1 && vi[nod] == -1))
srmq[0][vecin] = 1; /// altfel e 0
if (nod - vecin == 1 && vi[vecin] == -1){
rmq[0][vecin] = make_pair(nod , 0);
last[0][vecin] = srmq[0][vecin];
//printf ("%d\n", 0);
continue;
}
sol = DIMN;
query(1 , 1 , n , vecin , min(n , nod));
if (nod != n + 1){
rmq[0][vecin] = make_pair(nod , -sol - 1);
last[0][vecin] = srmq[0][vecin];
//printf ("%d\n", -sol - 1);
}
else {
rmq[0][vecin] = make_pair(nod , -sol);
last[0][vecin] = srmq[0][vecin];
//printf ("%d\n",-sol);
}
}
}
for (i = 1 ; i < 20 ; i++){
for (j = 1 ; j <= n ; j++){
rmq[i][j].first = rmq[i - 1][rmq[i - 1][j].first].first;
srmq[i][j] = srmq[i - 1][j] + srmq[i - 1][rmq[i - 1][j].first];
last[i][j] = last[i - 1][rmq[i - 1][j].first];
rmq[i][j].second = max(rmq[i - 1][j].second - ( sp[rmq[i][j].first] - sp[rmq[i - 1][j].first] + srmq[i][j] - srmq[i - 1][j]) ,
rmq[i - 1][rmq[i - 1][j].first].second);
/*if (srmq[0][rmq[i - 1][j].first] == 1){
if (rmq[i - 1][j].first + 1 == tt[rmq[i - 1][j].first])
else
rmq[i][j].second = max(rmq[i - 1][j].second - ( sp[rmq[i][j].first] - sp[rmq[i - 1][j].first] + 1) ,
rmq[i - 1][rmq[i - 1][j].first].second);
}
else {
rmq[i][j].second = max(rmq[i - 1][j].second - ( sp[rmq[i][j].first] - sp[rmq[i - 1][j].first] + 1) ,
rmq[i - 1][rmq[i - 1][j].first].second);
}*/
}
}
fread (buff , 1 , 8000000 , fin);
q = getnr();
//fscanf (fin,"%d",&q);
int correct , mini = DIMN , li , ri;
int deadd = 0 , ant;
for (int aux = 1 ; aux <= q ; aux++){
l = getnr();
r = getnr();
//fscanf (fin,"%d%d",&l,&r);
/*if (aux == 1874){
printf ("\n");
for (int k = l ; k <= r ; k++)
printf ("%d ", vi[k]);
printf ("\n");
printf ("a");
}*/
li = l;
ri = r;
maxi = 0;
//if (vi[li] == 1)
inc = 0;
//else inc = 0;
l = next_c[l];
if (l > r){
deadd = ri - li + 1;
inc = maxi = 0;
}
else {
deadd = l - li;
/*while (tt[l] <= r){
if (srmq[0][l]){
if (l + 1 != tt[l])
maxi = max(maxi - (sp[tt[l] - 1] - sp[l - 1]) , rmq[0][l].second);
}
inc += srmq[0][l];
ant = srmq[0][l];
l = tt[l];
}*/
maxi = 0;
inc = 0;
for (i = 19 ; i >= 0 ; i--){
fth = rmq[i][l].first;
if (fth <= r && fth){
if (last[i][l] == 1){
if (vi[l] != -1)
maxi = max(maxi - ( sp[fth] - sp[l - 1] + srmq[i][l] ) , rmq[i][l].second);
else
maxi = max(maxi - ( sp[fth] - sp[l] + srmq[i][l] ) , rmq[i][l].second);
}
else {
if (i == 0)
maxi = maxi;
else if (vi[l] != -1)
maxi = max(maxi - ( sp[fth - 1] - sp[l - 1] + srmq[i][l] ) , rmq[i][l].second + 1);
else
maxi = max(maxi - ( sp[fth - 1] - sp[l] + srmq[i][l] ) , rmq[i][l].second + 1);
}
inc += srmq[i][l];
ant = last[i][l];
l = fth;
}
}
/// l e < r
if (ant)
l++;
if (l <= r){
sol = DIMN;
query (1 , 1 , n , l , r);
maxi = max(maxi - ( sp[r] - sp[l - 1] ) , -sol);
}
}
/*fscanf (ans, "%d",&correct);
if (correct != inc + maxi + deadd){
mini = min(mini , ri - li + 1);
//printf ("Q");
if (ri - li + 1 == 5)
printf ("%d\n",aux);
}*/
fprintf (fout,"%d\n",inc + maxi + deadd);
}
//printf ("%d",mini);
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:127:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (j = 0 ; j < v[nod].size() ; j++){
| ~~^~~~~~~~~~~~~~~
election.cpp:198:9: warning: unused variable 'correct' [-Wunused-variable]
198 | int correct , mini = DIMN , li , ri;
| ^~~~~~~
election.cpp:198:19: warning: unused variable 'mini' [-Wunused-variable]
198 | int correct , mini = DIMN , li , ri;
| ^~~~
election.cpp:76:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
76 | fscanf (fin,"%d\n",&n);
| ~~~~~~~^~~~~~~~~~~~~~~
election.cpp:193:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
193 | fread (buff , 1 , 8000000 , fin);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:277:13: warning: 'ant' may be used uninitialized in this function [-Wmaybe-uninitialized]
277 | if (ant)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 2 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 3 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 4 |
Correct |
10 ms |
13420 KB |
Output is correct |
| 5 |
Correct |
10 ms |
13292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 2 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 3 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 4 |
Correct |
10 ms |
13420 KB |
Output is correct |
| 5 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 6 |
Correct |
124 ms |
39376 KB |
Output is correct |
| 7 |
Correct |
81 ms |
39276 KB |
Output is correct |
| 8 |
Correct |
95 ms |
39276 KB |
Output is correct |
| 9 |
Correct |
97 ms |
39276 KB |
Output is correct |
| 10 |
Correct |
116 ms |
39788 KB |
Output is correct |
| 11 |
Correct |
145 ms |
40300 KB |
Output is correct |
| 12 |
Correct |
107 ms |
39788 KB |
Output is correct |
| 13 |
Correct |
107 ms |
41068 KB |
Output is correct |
| 14 |
Correct |
103 ms |
39916 KB |
Output is correct |
| 15 |
Correct |
109 ms |
40428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 2 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 3 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 4 |
Correct |
10 ms |
13420 KB |
Output is correct |
| 5 |
Correct |
10 ms |
13292 KB |
Output is correct |
| 6 |
Correct |
124 ms |
39376 KB |
Output is correct |
| 7 |
Correct |
81 ms |
39276 KB |
Output is correct |
| 8 |
Correct |
95 ms |
39276 KB |
Output is correct |
| 9 |
Correct |
97 ms |
39276 KB |
Output is correct |
| 10 |
Correct |
116 ms |
39788 KB |
Output is correct |
| 11 |
Correct |
145 ms |
40300 KB |
Output is correct |
| 12 |
Correct |
107 ms |
39788 KB |
Output is correct |
| 13 |
Correct |
107 ms |
41068 KB |
Output is correct |
| 14 |
Correct |
103 ms |
39916 KB |
Output is correct |
| 15 |
Correct |
109 ms |
40428 KB |
Output is correct |
| 16 |
Correct |
961 ms |
198508 KB |
Output is correct |
| 17 |
Correct |
742 ms |
197996 KB |
Output is correct |
| 18 |
Correct |
795 ms |
198380 KB |
Output is correct |
| 19 |
Correct |
763 ms |
197868 KB |
Output is correct |
| 20 |
Correct |
984 ms |
201056 KB |
Output is correct |
| 21 |
Correct |
1477 ms |
206700 KB |
Output is correct |
| 22 |
Correct |
971 ms |
209172 KB |
Output is correct |
| 23 |
Correct |
1016 ms |
215288 KB |
Output is correct |
| 24 |
Correct |
949 ms |
211300 KB |
Output is correct |
| 25 |
Correct |
1006 ms |
214636 KB |
Output is correct |
