Submission #1240825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240825		abbvsss	Election (BOI18_election)	C++20	100 / 100	250 ms	35284 KiB

election

#include <bits/stdc++.h>
 
using namespace std;
 
const long long inf = 1e18; 
const int MOD = 1e9 + 7;

struct mi {
	int v;
	explicit operator int() const { return v; }
	mi() { v = 0; }
	mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
	if ((a.v += b.v) >= MOD) a.v -= MOD;
	return a;
}
mi &operator-=(mi &a, mi b) {
	if ((a.v -= b.v) < 0) a.v += MOD;
	return a;
}
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
mi &operator*=(mi &a, mi b) { return a = a * b; }
mi pow(mi a, long long p) {
	assert(p >= 0);
	return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
}
mi inv(mi a) {
	assert(a.v != 0);
	return pow(a, MOD - 2);
}
mi operator/(mi a, mi b) { return a * inv(b); }

template <class T>
void print(vector<T>& arr, bool __endl = true){
    for (int i = 0; i < arr.size(); i ++) cout << arr[i] << ' ';
    if (__endl)
    cout << '\n';
}

template <class T>
void input(vector<T>& arr){
    for (int i = 0; i < arr.size(); i ++) cin >> arr[i];
}

struct SegTreeNode{
    int L = 0, R = 0, S = 0, A = 0;
    SegTreeNode(){}
    SegTreeNode(int a, int b, int c, int d) : L(a), R(b), S(c), A(d) {}
    void combine(SegTreeNode u, SegTreeNode v){
        L = max(u.L, u.S + v.L);
        R = max(u.R + v.S, v.R);
        S = u.S + v.S;
        A = max(max(u.A + v.S, u.S + v.A), u.L + v.R);
    }
};

struct SegTree{
    vector<SegTreeNode> tree;
    int n;
    SegTree(int N, string& s){
        n = N;
        tree.resize(4 * n);
        build(0, 0, n - 1, s);
    }
    void build(int v, int l, int r, string& s){
        if (l == r){
            if (s[l] == 'T') tree[v] = SegTreeNode(1, 1, 1, 1);
            else tree[v] = SegTreeNode(0, 0, -1, 0);
            return;
        }
        int m = (l + r) / 2;
        build(2 * v + 1, l, m, s);
        build(2 * v + 2, m + 1, r, s);
        tree[v].combine(tree[2 * v + 1], tree[2 * v + 2]);
    }

    SegTreeNode query(int v, int tl, int tr, int l, int r){
        if (tl == l && tr == r) return tree[v];
        int m = (tl + tr) / 2;
        if (r <= m) return query(2 * v + 1, tl, m, l, r);
        if (l > m) return query(2 * v + 2, m + 1, tr, l, r);
        SegTreeNode ret;
        ret.combine(query(2 * v + 1, tl, m, l, m), query(2 * v + 2, m + 1, tr, m + 1, r));
        return ret; 
    }
};

// #define with_testcases
void t_main(signed __T){
    int n;
    cin >> n;
    string s;
    cin >> s;

    SegTree sg(n, s);

    int q;
    cin >> q;
    while (q --){
        int l, r;
        cin >> l >> r;
        --l; -- r;
        cout << sg.query(0, 0, n - 1, l, r).A << '\n';
    }
}
 
signed main(){
    cin.tie(nullptr) -> sync_with_stdio(false);
    int t = 1;
    #ifdef with_testcases
        cin >> t;
    #endif
    for (int i = 1; i <= t; i ++) {
        t_main(i);
        // cout << '\n';
    }
}

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