Submission #768891

#	Time	Username	Problem	Language	Result	Execution time	Memory
768891		pera	Election (BOI18_election)	C++17	0 / 100	7 ms	340 KiB

election

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

#define int long long

/*const int N = 5e5 + 1;

vector<int> t(4 * N);

void up(int v , int l , int r , int p , int x){
	if(l == r){
		t[v] = x;
	}else{
		int m = (l + r) / 2;
		if(p <= m) up(v * 2 , l , m , p , x);
		else up(v * 2 + 1 , m + 1 , r , p , x);
		t[v] = max(t[v * 2] , t[v * 2 + 1]);
	}
}

int g(int v , int l , int r , int L , int R){
	if(l > R || r < L || l > r) return 0;
	if(L <= l && r <= R) return t[v];
	int m = (l + r) / 2;
	return max(g(v * 2 , l , m , L , R) , g(v * 2 + 1 , m + 1 , r , L , R));
}*/

main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n;cin >> n;
	string S;cin >> S;
	vector<int> a(n + 1);
	for(int i = 0;i < n;i ++){
		a[i + 1] = (S[i] == 'C' ? 1 : -1);
	}
	/*vector<int> p(n + 1) , s(n + 2);
	for(int i = 1;i <= n;i ++){
		p[i] = p[i - 1] + a[i];
	}
	for(int i = n;i >= 1;i --){
		s[i] = s[i + 1] + a[i];
	}
	for(int i = 1;i <= n;i ++){
		up(1 , 1 , n , i , p[i] + s[i]);
	}*/
	int q;cin >> q;
	while(q --){
		int l , r;cin >> l >> r;
		int x = 0 , a1 = 0 , a2 = 0 , A = 0 , B = 0;
		for(int i = l;i <= r;i ++){
			if(a[i] == 1) ++ A;
			else ++ B;
		}
		for(int i = l;i <= r;i ++){
			if(a[i] == 1) a1 ++;
			else a2 ++;
			x = max(x , max(0LL , a2 - a1) + max(0LL , B - a2 - A + a1));
		}
		cout << max(0LL , x) << endl;
	}
}

Compilation message (stderr)

election.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main(){
      | ^~~~

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