Submission #381185

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381185	2021-03-24T17:35:04 Z	peijar	Election (BOI18_election)	C++17	100 / 100	940 ms	36348 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	492 KB	Output is correct
2	Correct	3 ms	492 KB	Output is correct
3	Correct	3 ms	492 KB	Output is correct
4	Correct	3 ms	492 KB	Output is correct
5	Correct	3 ms	492 KB	Output is correct

Subtask #2

54.0 / 54.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	492 KB	Output is correct
2	Correct	3 ms	492 KB	Output is correct
3	Correct	3 ms	492 KB	Output is correct
4	Correct	3 ms	492 KB	Output is correct
5	Correct	3 ms	492 KB	Output is correct
6	Correct	97 ms	7916 KB	Output is correct
7	Correct	86 ms	8044 KB	Output is correct
8	Correct	91 ms	7788 KB	Output is correct
9	Correct	81 ms	7788 KB	Output is correct
10	Correct	96 ms	7788 KB	Output is correct
11	Correct	92 ms	7980 KB	Output is correct
12	Correct	96 ms	7988 KB	Output is correct
13	Correct	95 ms	8044 KB	Output is correct
14	Correct	94 ms	7920 KB	Output is correct
15	Correct	94 ms	8044 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	492 KB	Output is correct
2	Correct	3 ms	492 KB	Output is correct
3	Correct	3 ms	492 KB	Output is correct
4	Correct	3 ms	492 KB	Output is correct
5	Correct	3 ms	492 KB	Output is correct
6	Correct	97 ms	7916 KB	Output is correct
7	Correct	86 ms	8044 KB	Output is correct
8	Correct	91 ms	7788 KB	Output is correct
9	Correct	81 ms	7788 KB	Output is correct
10	Correct	96 ms	7788 KB	Output is correct
11	Correct	92 ms	7980 KB	Output is correct
12	Correct	96 ms	7988 KB	Output is correct
13	Correct	95 ms	8044 KB	Output is correct
14	Correct	94 ms	7920 KB	Output is correct
15	Correct	94 ms	8044 KB	Output is correct
16	Correct	940 ms	35292 KB	Output is correct
17	Correct	764 ms	34796 KB	Output is correct
18	Correct	856 ms	35240 KB	Output is correct
19	Correct	690 ms	34556 KB	Output is correct
20	Correct	906 ms	34428 KB	Output is correct
21	Correct	933 ms	36348 KB	Output is correct
22	Correct	928 ms	36220 KB	Output is correct
23	Correct	921 ms	36348 KB	Output is correct
24	Correct	929 ms	36180 KB	Output is correct
25	Correct	912 ms	35452 KB	Output is correct