Submission #647484

#	Time	Username	Problem	Language	Result	Execution time	Memory
647484		UltraFalcon	Election (BOI18_election)	C++17	0 / 100	1 ms	340 KiB

election

#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt")
#endif

#include <bits/stdc++.h>
#define int long long

using namespace std;

int next_power_of_two(int x) { return 1LL<<(__lg(x-1)+1); }

struct Value {
    int inc, dec, sum;
    constexpr static Value Identity() { return {0, 0, 0}; }
    static Value Single(char x) {
        int val = (x == 'C') ? 1 : -1; 
        return {val<0, val<0, val}; 
    }
    friend Value combine(Value a, Value b) {
        Value res;
        res.inc = a.inc + max(0LL, (b.inc - max(0LL, a.sum + a.inc)));
        assert(a.sum + a.inc >= 0);
        res.dec = b.dec + max(0LL, (a.dec - max(0LL, b.sum + b.dec)));
        assert(b.sum + b.inc >= 0);
        res.sum = a.sum + b.sum;
        return res;
    }
};
struct Segtree {
    int n; 
    vector<Value> tree;

    Segtree(string& v) {
        n = next_power_of_two(v.size());
        tree.assign(2*n, Value::Identity());
        build(v, 0, 0, n);
    }

    public:
    Value query(int ql, int qr) {
        assert(0 <= ql && ql < qr && qr <= n);
        return query(ql, qr, 0, 0, n);
    }


    private:
    void recompute(int pos) {
        tree[pos] = combine(tree[pos*2+1], tree[pos*2+2]);
    }

    void build(string&v, int pos, int l, int r) {
        if (l >= (int)v.size()) return;
        if (l+1 == r) { tree[pos]=Value::Single(v[l]); return; }
        int m = (l+r) / 2;
        build(v, pos*2+1, l, m);
        build(v, pos*2+2, m, r);
        recompute(pos);
    }

    Value query(int ql, int qr, int pos, int l, int r) {
        if (ql >= r || qr <= l) return Value::Identity();
        if (ql <= l && qr >= r) return tree[pos];
        int m = (l+r) / 2;
        return combine(
            query(ql, qr, pos*2+1, l, m),
            query(ql, qr, pos*2+2, m, r)
        );
    }
};

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

    // Value a = {0, 2, 1};
    // Value b = {4, 2, -2};
    // Value res = combine(a, b);
    // cout << res.inc << " " << res.dec << "\n";

    int n; cin >> n;
    string votes; cin >> votes;
    
    Segtree seg(votes);
    
    int q; cin >> q;
    for (int i=0; i<q; i++) {
        int l, r;
        cin >> l >> r;
        Value res = seg.query(l-1, r);
        cout << max(res.inc, res.dec) << "\n";
    }

}

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