Submission #624772

#	Time	Username	Problem	Language	Result	Execution time	Memory
624772		NintsiChkhaidze	Election (BOI18_election)	C++14	82 / 100	139 ms	20012 KiB

election

#include <bits/stdc++.h>
#define pb push_back
#define tree int h,int l,int r
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 200005;
string s;

struct {
	int l = 0; // max prefix sum
	int r = 0; // max suffix sum
	int s = 0; 
	int ans = 0; 
} t[4*N];
void UPDnode(int h){
	t[h].s = t[h*2].s + t[h*2 + 1].s;
	
	t[h].l = max(t[h*2].l,t[h*2].s + t[h*2 + 1].l);
	t[h].r = max(t[h*2 + 1].r,t[h*2].r + t[h*2+1].s);
	
	t[h].ans = max({t[h*2].ans + t[h*2+1].s,t[h*2+1].ans + t[h*2].s,t[h*2].l + t[h*2 + 1].r});
}
void U(int h,int l){
	if (s[l] == 'C') {
		t[h].ans = t[h].l = 0,t[h].r = 0;
		t[h].s = -1;
	}else{
		t[h].s = t[h].ans = t[h].l = t[h].r = 1;
	}
}
void build(tree){
	if (l == r){
		U(h,l);	
		return;
	}
	build(left);
	build(right);
	UPDnode(h);
}

vector <int> get(tree,int L,int R){
	if (r < L || R < l) return {0,0,0,0};
	if (L <= l && r <= R) return {t[h].l,t[h].r,t[h].s,t[h].ans};
	vector <int> x = get(left,L,R),y = get(right,L,R),z = {0,0,0,0};
	z[2] = x[2] + y[2];
	z[0] = max(x[0],x[2] + y[0]);
	z[1] = max(y[1],x[1] + y[2]);
	z[3] = max({x[3] + y[2],y[3] + x[2],x[0] + y[1]});
	return z;
}
main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n;
	cin>>n;
	cin>>s;
	s='%' + s;
	
	build(1,1,n);
	int m;
	cin>>m;
	for (int i = 1; i <= m; i++){
		int l,r;
		cin>>l>>r;
		vector <int> res = get(1,1,n,l,r);
		cout<<res[3]<<"\n";
	}
	
}

Compilation message (stderr)

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

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