Submission #346312

#	Time	Username	Problem	Language	Result	Execution time	Memory
346312		Ruxandra985	Election (BOI18_election)	C++14	100 / 100	1477 ms	215288 KiB

election

#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 (stderr)

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)
      |             ^~

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18