Submission #648461

#	Time	Username	Problem	Language	Result	Execution time	Memory
648461		andrei_marciuc	Election (BOI18_election)	C++17	100 / 100	1463 ms	28056 KiB

election

#include <iostream>
using namespace std;
const int N = 2e6 + 7;
int n, q, m, a[ N ]; 
string s;
struct node {
	int minimum_result;
	int sum;
	int minl;
	int minr;
};

node tree[ N ];
node join( node x, node y ) {
	return {
		max( x.minl + y.minr, max( x.sum + y.minimum_result, x.minimum_result + y.sum ) ), 
		x.sum + y.sum, 
		max( x.minl, x.sum + y.minl ),
		max( y.minr, y.sum + x.minr )
	};
}

void build( int poz, int l, int r, int pos, int val ) {
	if( l > r || r < pos || l > pos ) 
		return;
	if( l == r ) {
		tree[ poz ].sum = val;
		tree[ poz ].minl = max( tree[ poz ].minl, val );
		tree[ poz ].minr = max( tree[ poz ].minr, val );
		tree[ poz ].minimum_result = max( tree[ poz ].minimum_result, val );
		return;
	}

	int med = ( l + r ) / 2;
	build( poz * 2, l, med, pos, val );
	build( poz * 2 + 1, med + 1, r, pos, val );
	tree[ poz ] = join( tree[ poz * 2 ], tree[ poz * 2 + 1 ] );
}

node get( int poz, int l, int r, int u, int v ) {
	if( l > v || r < u ) 
		return { 0, 0, 0, 0 };
	if( l >= u && r <= v ) 
		return tree[ poz ];
	int med = ( l + r ) / 2;
	return join( get( poz * 2, l, med, u, v ), get( poz * 2 + 1, med + 1, r, u, v ) );
}

int main()
{
	cin >> n >> s >> q;
	for( int i = 0; i < n; i++ ) 
		if( s[ i ] == 'C' ) 
			build( 1, 1, n, i + 1, -1 ); 
		else build( 1, 1, n, i + 1, 1 );
	
	while( q-- ) {
		int l,r;
		cin >> l >> r;
		cout << get( 1, 1, n, l, r ).minimum_result << '\n';
	}
	return 0;
}

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