Submission #442020

#	Time	Username	Problem	Language	Result	Execution time	Memory
442020		penguinhacker	Election (BOI18_election)	C++14	0 / 100	1 ms	588 KiB

election

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e5;
int n, q, lg[mxN+1], st1[mxN][19], st2[mxN][19];
string s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s >> q;
	for (int i=0; i<n; ++i)
		st1[i][0]=(i?st1[i-1][0]:0)+(s[i]=='T'?1:-1);
	for (int i=n-1; ~i; --i)
		st2[i][0]=(i+1<n?st2[i+1][0]:0)+(s[i]=='T'?1:-1);
	for (int i=2; i<=n; ++i)
		lg[i]=lg[i/2]+1;
	for (int j=1; 1<<j<=n; ++j)
		for (int i=0; i+(1<<j)-1<n; ++i) {
			st1[i][j]=max(st1[i][j-1], st1[i+(1<<j-1)][j-1]);
			st2[i][j]=max(st2[i][j-1], st2[i+(1<<j-1)][j-1]);
		}
	while(q--) {
		int l, r;
		cin >> l >> r, --l, --r;
		int k=lg[r-l+1];
		int a1=max(st1[l][k], st1[r-(1<<k)+1][k])-(l?st1[l-1][0]:0);
		int a2=max(st2[l][k], st2[r-(1<<k)+1][k])-(r+1<n?st2[r+1][0]:0);
		cout << max({0, a1, a2}) << "\n";
	}
	return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:23:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |    st1[i][j]=max(st1[i][j-1], st1[i+(1<<j-1)][j-1]);
      |                                         ~^~
election.cpp:24:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |    st2[i][j]=max(st2[i][j-1], st2[i+(1<<j-1)][j-1]);
      |                                         ~^~

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