Submission #1278208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278208		chr34	Election (BOI18_election)	C++20	100 / 100	514 ms	36660 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
const int INF = 1e18;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

struct Node{
    int l_max, r_max, tot, ans;

    Node operator+(Node b){
        Node ret;
        ret.l_max = max(l_max, b.l_max + tot);
        ret.r_max = max(r_max +b.tot, b.r_max);
        ret.tot = tot + b.tot;
        ret.ans = max(l_max + b.r_max, max(ans + b.tot, b.ans + tot));
        return ret;
    } 
};

int n;
Node segtree[2000001];
char s[500001];

void build(int node = 1, int l = 1, int r = n){
    if(l == r){
        if(s[l] == 'T') segtree[node] = {1, 1, 1, 1};
        else segtree[node] = {0, 0, -1, 0};
    }
    else{
        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
        segtree[node] = segtree[2 * node] + segtree[2 * node + 1];
    }
}

Node query(int a, int b, int node = 1, int l = 1, int r = n){
    if(l > b || r < a) return {0, 0, 0, 0};
    if(l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    Node p1 = query(a, b, 2 * node, l, mid);
    Node p2 = query(a, b, 2 * node + 1, mid + 1, r);
    return p1 + p2;
}

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.in", "r", stdin);
	//freopen("input.out", "w", stdout);    
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
    }
    build();
    int q; cin >> q;
    while(q--){
        int a, b; cin >> a >> b;
        cout<<query(a, b).ans<<endl;
    }
    return 0;
}

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