oj.uz

Submission #442020

# Submission time Handle Problem Language Result Execution time Memory
442020 2021-07-06T19:02:18 Z penguinhacker Election (BOI18_election) C++14
0 / 100
 1 ms 588 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -