oj.uz

Submission #648461

# Submission time Handle Problem Language Result Execution time Memory
648461 2022-10-06T16:01:44 Z andrei_marciuc Election (BOI18_election) C++17
100 / 100
 1463 ms 28056 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 5 ms 324 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 5 ms 328 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 5 ms 324 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 179 ms 5784 KB Output is correct
7 Correct 176 ms 5728 KB Output is correct
8 Correct 179 ms 5824 KB Output is correct
9 Correct 187 ms 5700 KB Output is correct
10 Correct 180 ms 5672 KB Output is correct
11 Correct 179 ms 5756 KB Output is correct
12 Correct 187 ms 5812 KB Output is correct
13 Correct 182 ms 5848 KB Output is correct
14 Correct 187 ms 5836 KB Output is correct
15 Correct 199 ms 5736 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 5 ms 324 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 179 ms 5784 KB Output is correct
7 Correct 176 ms 5728 KB Output is correct
8 Correct 179 ms 5824 KB Output is correct
9 Correct 187 ms 5700 KB Output is correct
10 Correct 180 ms 5672 KB Output is correct
11 Correct 179 ms 5756 KB Output is correct
12 Correct 187 ms 5812 KB Output is correct
13 Correct 182 ms 5848 KB Output is correct
14 Correct 187 ms 5836 KB Output is correct
15 Correct 199 ms 5736 KB Output is correct
16 Correct 1463 ms 27148 KB Output is correct
17 Correct 1319 ms 26576 KB Output is correct
18 Correct 1377 ms 26960 KB Output is correct
19 Correct 1298 ms 26248 KB Output is correct
20 Correct 1418 ms 26256 KB Output is correct
21 Correct 1445 ms 27828 KB Output is correct
22 Correct 1416 ms 27864 KB Output is correct
23 Correct 1417 ms 28056 KB Output is correct
24 Correct 1409 ms 27712 KB Output is correct
25 Correct 1405 ms 27268 KB Output is correct