Submission #1266867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266867		bbldrizzy	Election (BOI18_election)	C++20	100 / 100	300 ms	20280 KiB

election

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <random>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll inf = 4*1e18;
const int mx = 5*1e5+5;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
struct Node {
    int l, r, s, a;

    Node operator+(Node b) {
        Node ret;
        ret.l = max(l, s+b.l);
        ret.r = max(r+b.s, b.r);
        ret.s = s + b.s;
        ret.a = max({a+b.s, s+b.a, l+b.r});
        return ret;
    }
};

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

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

Node query(int v, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) {return {0, 0, 0, 0};}
    if (ql >= l && qr <= r) return segtree[v];
    int mid = (ql+qr)/2;
    Node x = query(2*v, l, r, ql, mid)+query(2*v+1, l, r, mid+1, qr); 
    return x; 
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    build(1, 1, n);
    int q; cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        cout << query(1, a, b, 1, n).a << "\n";
    }
}

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