Submission #1017820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017820		KN200711	Election (BOI18_election)	C++14	100 / 100	374 ms	29968 KiB

election

# include <bits/stdc++.h>
# define ll long long
# define ld double
# define fi first
# define se second
# define pii pair<int, int>
# define pll pair<ll, ll>
using namespace std;

int val[500001];
pair<pii, pii> seg[2000020];

void build(int lf, int rg, int nd) {
	if(lf == rg) {
		seg[nd].fi.fi = val[lf];
		seg[nd].fi.se = seg[nd].se.fi = seg[nd].se.se = max(0, val[lf]);
	} else {
		int mid = (lf + rg) / 2;
		build(lf, mid, 2*nd+1);
		build(mid+1, rg, 2*nd+2);
		
		seg[nd].fi.fi = seg[2*nd + 1].fi.fi + seg[2*nd + 2].fi.fi;
		seg[nd].fi.se = max(seg[2*nd + 1].fi.se, seg[2*nd + 1].fi.fi + seg[2*nd + 2].fi.se);
		seg[nd].se.fi = max(seg[2*nd+2].se.fi, seg[2*nd+2].fi.fi + seg[2*nd+1].se.fi);
		seg[nd].se.se = max(seg[2*nd + 1].fi.se + seg[2*nd + 2].se.fi, max(seg[2*nd + 1].fi.fi + seg[2*nd + 2].se.se, seg[2*nd + 1].se.se + seg[2*nd + 2].fi.fi));
		
	}
}

pair<pii, pii> qry(int lf, int rg, int nd, int clf, int crg) {
	if(lf > crg || clf > rg) {
		return {{0, 0}, {0, 0}};
	} else if(clf <= lf && rg <= crg) return seg[nd];
	int mid = (lf + rg) / 2;
	
	pair<pii, pii> nw, l, r;
	l = qry(lf, mid, 2*nd+1, clf, crg);
	r = qry(mid+1, rg, 2*nd+2, clf, crg);
	
	nw.fi.fi = l.fi.fi + r.fi.fi;
	nw.fi.se = max(l.fi.se, l.fi.fi + r.fi.se);
	nw.se.fi = max(r.se.fi, r.fi.fi + l.se.fi);
	nw.se.se = max(l.fi.se + r.se.fi, max(l.fi.fi + r.se.se, l.se.se + r.fi.fi));
	
	return nw;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	cin>>N;
	
	string S;
	cin>>S;
	
	for(int i=1;i<=N;i++) {
		if(S[i - 1] == 'C') val[i] = -1;
		else val[i] = 1;
	}
	
	build(1, N, 0);
	int Q;
	cin>>Q;
	while(Q--) {
		int L, R;
		cin>>L>>R;
		
		cout<<qry(1, N, 0, L, R).se.se<<"\n";
	}
	return 0;
}

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