Submission #381185

#	Time	Username	Problem	Language	Result	Execution time	Memory
381185		peijar	Election (BOI18_election)	C++17	100 / 100	940 ms	36348 KiB

election

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

const int MAXN = 2e6;

struct Noeud
{
	int iDeb, iFin;
	int maxPref, maxSuff, totDelta, sol;
};

Noeud fusion(Noeud lhs, Noeud rhs)
{
	Noeud ret;
	ret.iDeb = lhs.iDeb;
	ret.iFin = rhs.iFin;
	ret.maxPref = max(lhs.maxPref, lhs.totDelta + rhs.maxPref);
	ret.maxSuff = max(rhs.maxSuff, rhs.totDelta + lhs.maxSuff);
	ret.sol = max({lhs.totDelta + rhs.sol, lhs.sol + rhs.totDelta, lhs.maxPref + rhs.maxSuff});
	ret.totDelta = lhs.totDelta + rhs.totDelta;
	return ret;
}

Noeud seg[MAXN];

string votes;

void construitArbre(int iNoeud, int iDeb, int iFin)
{
	if (iDeb == iFin)
	{
		seg[iNoeud].iDeb = iDeb;
		seg[iNoeud].iFin = iFin;
		int val = votes[iDeb] == 'T' ? 1 : 0;
		seg[iNoeud].maxPref = seg[iNoeud].maxSuff = seg[iNoeud].sol = seg[iNoeud].totDelta = val;
		if (votes[iDeb] == 'C')
			seg[iNoeud].totDelta = -1;
		return;
	}
	construitArbre(2*iNoeud, iDeb, (iDeb+iFin)/2);
	construitArbre(2*iNoeud+1, (iDeb+iFin)/2+1, iFin);
	seg[iNoeud] = fusion(seg[2*iNoeud], seg[2*iNoeud+1]);
}

Noeud requete(int iNoeud, int iDeb, int iFin)
{
	if (iDeb <= seg[iNoeud].iDeb and seg[iNoeud].iFin <= iFin)
		return seg[iNoeud];
	if (iDeb > seg[iNoeud].iFin or iFin < seg[iNoeud].iDeb)
		return {0, 0, 0, 0, 0, 0};
	return fusion(requete(2*iNoeud, iDeb, iFin), requete(2*iNoeud+1, iDeb, iFin));
}

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbFans;
	cin >> nbFans >> votes;
	construitArbre(1, 0, nbFans-1);

	int nbRequetes;
	cin >> nbRequetes;
	for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) 
	{
		int L, R;
		cin >> L >> R;
		cout << requete(1, L-1, R-1).sol << '\n';
	}
}

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