oj.uz

Submission #757817

# Submission time Handle Problem Language Result Execution time Memory
757817 2023-06-13T18:59:32 Z LucaIlie Election (BOI18_election) C++17
0 / 100
 28 ms 47316 KB 
#include <bits/stdc++.h>

using namespace std;

struct query {
    int l, r, i;
};

const int MAX_N = 5e5 + 2;
int bucketSize, elim = 0;
bool outLR[MAX_N], outRL[MAX_N];
int vote[MAX_N], sumVoteLR[MAX_N], sumVoteRL[MAX_N], ans[MAX_N];
query queries[MAX_N];
vector<int> positionsLR[2 * MAX_N + 1], positionsRL[2 * MAX_N + 1];

void markLR( int i, bool b ) {
    elim -= (outLR[i] | outRL[i]);
    outLR[i] = b;
    elim += (outLR[i] | outRL[i]);
}

void markRL( int i, bool b ) {
    elim -= (outLR[i] | outRL[i]);
    outRL[i] = b;
    elim += (outLR[i] | outRL[i]);
}

int firstPos( int l, int val ) {
    val += MAX_N;
    if ( lower_bound( positionsLR[val].begin(), positionsLR[val].end(), l ) == positionsLR[val].end() )
        return -1;
    return *lower_bound( positionsLR[val].begin(), positionsLR[val].end(), l );
}

int lastPos( int r, int val ) {
    val += MAX_N;
    if ( upper_bound( positionsRL[val].begin(), positionsRL[val].end(), r ) == positionsRL[val].begin() )
        return -1;
    auto p = upper_bound( positionsRL[val].begin(), positionsRL[val].end(), r );
    p--;
    return *p;
}

int main() {
    int n, q;

    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        char ch;
        cin >> ch;
        vote[i] = (ch == 'C' ? 1 : -1);
    }

    for ( int i = 1; i <= n; i++ )
        sumVoteLR[i] = sumVoteLR[i - 1] + vote[i];
    for ( int i = n; i >= 1; i-- )
        sumVoteRL[i] = sumVoteRL[i + 1] + vote[i];
    for ( int i = 0; i <= n; i++ )
        positionsLR[sumVoteLR[i] + MAX_N].push_back( i );
    for ( int i = 1; i <= n + 1; i++ )
        positionsRL[sumVoteRL[i] + MAX_N].push_back( i );

    cin >> q;
    bucketSize = sqrt( (long long)n * n / q );
    for ( int i = 0; i < q; i++ ) {
        int l, r;
        cin >> queries[i].l >> queries[i].r;
        queries[i].i = i;
    }

    sort( queries, queries + q, [] ( query a, query b ) {
        if ( (a.l - 1) / bucketSize == (b.l - 1) / bucketSize )
            return a.r < b.r;
        return (a.l - 1) / bucketSize < (b.l - 1) / bucketSize;
    } );

    int l = 1, r = 0;
    for ( int i = 0; i < q; i++ ) {
        while ( l > queries[i].l ) {
            l--;
            if ( vote[l] == +1 ) {
                int pos = firstPos( l, sumVoteLR[l] - 1 );
                if ( pos != -1 )
                    markLR( pos, false );
            } else {
                markLR( l, true );
                /*if ( sumVoteLR[r] - sumVoteLR[l - 1] < 0 )
                    markLR( r, true );
                if ( sumVoteRL[l] - sumVoteRL[r + 1] < 0 )
                    markRL( l, true );*/
            }
        }

        /*printf( "%d %d\n", l, r );
        for ( int j = 0; j < n; j++ )
            printf( "%d", outLR[j] );
        printf( "\n" );
        for ( int j = 0; j < n; j++ )
            printf( "%d", outRL[j] );
        printf( "\n" );*/

        while ( r < queries[i].r ) {
            r++;
            if ( vote[r] == +1 ) {
                int pos = lastPos( r, sumVoteRL[r] - 1 );
                if ( pos != -1 )
                    markRL( pos, false );
            } else {
                markRL( r, true );
                /*if ( sumVoteLR[r] - sumVoteLR[l - 1] < 0 )
                    markLR( r, true );
                if ( sumVoteRL[l] - sumVoteRL[r + 1] < 0 )
                    markRL( l, true );*/
            }
        }

        while ( l < queries[i].l ) {
            if ( vote[l] == +1 ) {
                int pos = firstPos( l, sumVoteLR[l - 1] );
                if ( pos != -1 )
                    markLR( pos, true );
                /*if ( sumVoteLR[r] - sumVoteLR[l] < 0 )
                    markLR( r, true );
                if ( sumVoteRL[l + 1] - sumVoteRL[r + 1] < 0 )
                    markRL( l + 1, true );*/
            } else {
                int pos = firstPos( l + 1, sumVoteLR[l - 1] - 1 );
                if ( pos != -1 )
                    markLR( pos, false );
            }
            l++;
        }
        while ( r > queries[i].r ) {
            if ( vote[r] == +1 ) {
                int pos = lastPos( r, sumVoteRL[r + 1] );
                if ( pos != -1 )
                    markRL( pos, true );
                /*if ( sumVoteLR[r - 1] - sumVoteLR[l - 1] < 0 )
                    markLR( r - 1, true );
                if ( sumVoteRL[l] - sumVoteRL[r] < 0 )
                    markRL( l, true );*/
            } else {
                int pos = lastPos( r - 1, sumVoteLR[r + 1] - 1 );
                if ( pos != -1 )
                    markRL( pos, false );
            }
            r--;
        }


        ans[queries[i].i] = elim;
    }

    for ( int i = 0; i < q; i++ )
        cout << ans[i] << "\n";

    return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:66:13: warning: unused variable 'l' [-Wunused-variable]
   66 |         int l, r;
      |             ^
election.cpp:66:16: warning: unused variable 'r' [-Wunused-variable]
   66 |         int l, r;
      |                ^

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 47316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 47316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 47316 KB Output isn't correct
2 Halted 0 ms 0 KB -