Submission #345844

#	Time	Username	Problem	Language	Result	Execution time	Memory
345844		Ruxandra985	Election (BOI18_election)	C++14	0 / 100	8 ms	492 KiB

election

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

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

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