oj.uz

답안 #381185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381185 2021-03-24T17:35:04 Z peijar Election (BOI18_election) C++17
100 / 100
 940 ms 36348 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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