Submission #758110

#	Time	Username	Problem	Language	Result	Execution time	Memory
758110		LucaIlie	Election (BOI18_election)	C++17	0 / 100	30 ms	47284 KiB

election

#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 5e5 + 2;
int bucketSize, elim = 0, elimLR = 0, elimRL = 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]);
    elimLR -= outLR[i];
    outLR[i] = b;
    elim += (outLR[i] | outRL[i]);
    elimLR += outLR[i];
}

void markRL( int i, bool b ) {
    elim -= (outLR[i] | outRL[i]);
    elimRL += outRL[i];
    outRL[i] = b;
    elim += (outLR[i] | outRL[i]);
    elimRL += 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;
    for ( int i = 0; i < q; i++ ) {
        int l, r, ans = 0;
        cin >> l >> r;
        for ( int j = l; j <= r; j++ ) {
            ans = min( ans, sumVoteLR[j] - sumVoteLR[l - 1] );
            ans = min( ans, sumVoteRL[j] - sumVoteRL[r + 1] );
        }
        cout << -ans << "\n";
    }

    return 0;
}

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