Submission #647100

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
647100	2022-10-01 15:02:20	Alenygam	Election (BOI18_election)	C++14	100 / 100	633 ms	41416 KiB

election

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
struct Node {
    long long mpf = 0;
    long long msf = 0;
    long long sum = 0;
    long long ans = 0;
};
struct SegTree {
    vector<Node> segTree;
    int realSize;
    SegTree(int N, string &data) {
        realSize = 1<<(int)ceil(log2(N));
        segTree.resize(realSize * 2);
        for (int i = 0; i < N; i++) {
            if (data[i] == 'T') segTree[realSize + i] = {1, 1, 1, 1};
            else segTree[realSize + i] = {0, 0, -1, 0};
        }
        for (int i = realSize - 1; i > 0; i--) {
            segTree[i].mpf = max(segTree[i * 2].mpf, segTree[i * 2].sum + segTree[i * 2 + 1].mpf);
            segTree[i].msf = max(segTree[i * 2 + 1].msf, segTree[i * 2 + 1].sum + segTree[i * 2].msf);
            segTree[i].sum = segTree[i * 2].sum + segTree[i * 2 + 1].sum;
            segTree[i].ans = max({
                segTree[i * 2].sum + segTree[i * 2 + 1].ans,
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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