Submission #1240746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240746		abbvsss	Election (BOI18_election)	C++20	0 / 100	1 ms	576 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 t_count = 0, c_count = 0, diff = 0;
    SegTreeNode(){}
    SegTreeNode(int t, int c, int d) : t_count(t), c_count(c), diff(d) {}
};

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

        tree[v].t_count = tree[2 * v + 1].t_count + tree[2 * v + 2].t_count;
        tree[v].c_count = tree[2 * v + 1].c_count + tree[2 * v + 2].c_count;
        tree[v].diff = max(tree[2 * v + 1].diff, tree[2 * v + 2].diff + tree[2 * v + 1].t_count - tree[2 * v + 1].c_count);
    }
    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 left = query(2 * v + 1, tl, m, l, m);
        SegTreeNode right = query(2 * v + 2, m + 1, tr, m + 1, r);
        SegTreeNode ret = SegTreeNode();
        ret.t_count = left.t_count + right.t_count;
        ret.c_count = left.c_count + right.c_count;
        ret.diff = max(left.diff, right.diff + left.t_count - left.c_count);
        return ret;
    }
    int query(int l, int r){
        return max(0, query(0, 0, n - 1, l, r).diff);
    }
};

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

        tree[v].t_count = tree[2 * v + 1].t_count + tree[2 * v + 2].t_count;
        tree[v].c_count = tree[2 * v + 1].c_count + tree[2 * v + 2].c_count;
        tree[v].diff = max(tree[2 * v + 2].diff, tree[2 * v + 1].diff + tree[2 * v + 2].t_count - tree[2 * v + 2].c_count);
    }
    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 left = query(2 * v + 1, tl, m, l, m);
        SegTreeNode right = query(2 * v + 2, m + 1, tr, m + 1, r);
        SegTreeNode ret = SegTreeNode();;
        ret.t_count = left.t_count + right.t_count;
        ret.c_count = left.c_count + right.c_count;
        ret.diff = max(right.diff, left.diff + right.t_count - right.c_count);
        return ret;
    }
    int query(int l, int r){
        return max(0, query(0, 0, n - 1, l, r).diff);
    }
};

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

    int q;
    cin >> q;
    while (q --){
        int l, r;
        cin >> l >> r;
        --l; -- r;
        // cout << l << ' ' << r << '\n';
        // cout << sglr.query(l, r) << ' ' << sgrl.query(l, r) << '\n';
        cout << max(sglr.query(l, r), sgrl.query(l, r)) << '\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: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18