Submission #418698

#	Time	Username	Problem	Language	Result	Execution time	Memory
418698		timg8710	Election (BOI18_election)	C++17	0 / 100	2 ms	588 KiB

election

//Author: timg8710

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, int> pii;
 
#define pb push_back
 
#define f first
#define s second

struct node{
    int sum;
    int left; int right;
    node(int v){
        sum = v;
        left = min(0, v); right = min(0, v);
    }
    node(){
        sum = left = right = 0;
    }
    node comb(node& other){
        node h;
        h.sum = sum + other.sum;
        h.left = min(left, sum + other.left);
        h.right = min(other.right, other.sum + right);
        return h;
    }
};

template <typename T>
struct segtree
{
    T none; //comb(a, none) = a

    T val;
    int gL, gR, mid;
    segtree<T> *left;
    segtree<T> *right;

    T comb(T& l, T& r)
    {
        return l.comb(r);
    }

    segtree(int l, int r, T arr[], T non)
    { //modify arr type
        none = non;
        gL = l; gR = r; mid = (gL+gR)/2;
        if (l == r)
        {
            val = arr[l];
        }
        else
        {
            left = new segtree<T>(l, mid, arr, non); right = new segtree<T>(mid + 1, r, arr, non);
            val = comb(
                left->val, right->val);
        }
    }

    T query(int l, int r)
    {

        if (gL > r || gR < l)
        {
            return none;
        }

        if (gL == l && gR == r)
        {
            return val;
        }
        T a = left->query(l, min(r, mid)); T b = right->query(max(l, mid + 1), r);
        return comb(a, b); //might be wrong
    }

    void update(int idx, T set)
    {
        if (gL == gR)
        {
            val = set;
        }
        else
        {
            if (idx <= (gL + gR) / 2)
            {
                left->update(idx, set);
            }
            else
            {
                right->update(idx, set);
            }
            val = comb(left->val, right->val);
        }
   }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, q, u, v;
    char c;
    cin >> n;
    node nums[n];
    for(int i = 0; i<n; i++) {
        cin >> c; 
        nums[i] = node((c == 'T' ? -1 : 1));
    }
    cin >> q;
    segtree<node> sgt(0,n-1, nums, node());
    while(q--){
        cin >> u; cin >> v;
        node res = sgt.query(u-1, v-1);
        cout << -min(res.left, res.right) << "\n";
    }
    return 0;
}

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