Submission #760458

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
760458	2023-06-17 15:46:16	vjudge1	Election (BOI18_election)	C++17	100 / 100	377 ms	27908 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;
            int N, Q; string S;
            struct node{
                int sum, pref, suff, res;
            } ST[4 * 500005];
            node merge(node A, node B) {
                node C;
                C.sum = A.sum + B.sum;
                C.pref = max(A.pref, A.sum + B.pref);
                C.suff = max(B.suff, B.sum + A.suff);
                C.res = max({A.pref + B.suff, A.res + B.sum, A.sum + B.res});
                return C;
            }
            void build(int v, int l, int r) {
                if(l == r) {
                    if(S[l] == 'C') ST[v] = {-1, 0, 0, 0};
                    if(S[l] == 'T') ST[v] = {1, 1, 1, 1};
                    return;
                }
                build(v * 2, l, (l + r) / 2);
                build(v * 2 + 1, (l + r) / 2 + 1, r);
                ST[v] = merge(ST[v * 2], ST[v * 2 + 1]);
            }
            node query(int v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return {0, 0, 0, 0};
                if(l >= lo && r <= hi) return ST[v];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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