#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> positions[2 * MAX_N];
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 ) {
return -1;
if ( lower_bound( positions[val].begin(), positions[val].end(), l ) == positions[val].end() )
return -1;
return *lower_bound( positions[val].begin(), positions[val].end(), l );
}
int lastPos( int r, int val ) {
return -1;
if ( upper_bound( positions[val].begin(), positions[val].end(), r ) == positions[val].begin() )
return -1;
auto p = upper_bound( positions[val].begin(), positions[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];
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 );
}
}
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, false );
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:63:13: warning: unused variable 'l' [-Wunused-variable]
63 | int l, r;
| ^
election.cpp:63:16: warning: unused variable 'r' [-Wunused-variable]
63 | int l, r;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
