Submission #572029

#	Time	Username	Problem	Language	Result	Execution time	Memory
572029		Doanxem99	Election (BOI18_election)	C++14	82 / 100	59 ms	31984 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define ar array< int , 2>
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
template<typename T1, typename T2> bool minN(T1 &a, T2 b) {if (a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxX(T1 &a, T2 b) {if (a < b) a = b; else return 0; return 1;}
const int MAX = 1e6 + 1000;
int n, k, Size, x, y;
string s;
struct Node
{
    int sum = 0, minEraL = 0, minEraR = 0, ans = 0;
};
Node f[MAX], base;
Node Cal(Node a, Node b)
{
    Node c;
    c.sum = a.sum + b.sum;
    c.minEraL = max(a.minEraL, a.sum + b.minEraL);
    c.minEraR = max(b.minEraR, b.sum + a.minEraR);
    c.ans = max({a.minEraL + b.minEraR, a.sum + b.ans, a.ans + b.sum});
    return c;
}
void Build(int id, int l, int r)
{
    if (l > r) return;
    if (l == r)
    {
        int temp = (s[l] == 'C' ? -1 : (s[l] == 'T') ? 1 : 0);
        //cout << l << " " << temp << " " << id << '\n' ;
        f[id].sum = temp;
        maxX(f[id].minEraL, temp);
        maxX(f[id].minEraR, temp);
        maxX(f[id].ans, temp);
        return ;
    }
    int mid = (l + r) >> 1;
    Build(id * 2, l, mid);
    Build(id * 2 + 1, mid + 1, r);
    f[id] = Cal(f[id * 2], f[id * 2 + 1]);
}
Node Get(int id, int l, int r, int ll, int rr)
{
    if (ll > rr || rr < l || ll > r) return base;
    if (l <= ll && rr <= r) return f[id];
    int mid = (ll + rr) >> 1;
    return Cal(Get(id * 2, l, r, ll, mid), Get(id * 2 + 1, l, r, mid + 1, rr));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    Size = 1;
    while (Size < n) Size *= 2;
    cin >> s;
    s = "#" + s;
    //for (int i = n; i <= Size; i++) s = s + "#";
    Build(1, 1, n);
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> x >> y;
        cout << Get(1, x, y, 1, n).ans << '\n' ;
    }
    //cout << Get(1, 4, 9, 1, n).sum << '\n' ;
}
/*
11
CCCTTTTTTCC
3
1 11
4 9
1 6

*/

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