Submission #549486

#	Time	Username	Problem	Language	Result	Execution time	Memory
549486		MohamedFaresNebili	Election (BOI18_election)	C++14	100 / 100	512 ms	28004 KiB

election

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        /// #define int ll

        const int oo = 1e9 + 7;

        int n, q; string s;
        struct node{
            int S, pr, sf, ans;
        } st[2000001];

        node merge(node u, node v) {
            node res;
            res.S = u.S + v.S;
            res.pr = max(u.pr, u.S + v.pr);
            res.sf = max(v.sf, v.S + u.sf);
            res.ans = max({u.pr + v.sf, u.ans + v.S, u.S + v.ans});
            return res;
        }
        void build(int v, int l, int r) {
            if(l == r) {
                if(s[l] == 'C') st[v] = {-1, 0, 0, 0};
                else st[v] = {1, 1, 1, 1};
                return;
            }
            build(v * 2, l, (l + r) / 2);
            build(v * 2 + 1, (l + r) / 2 + 1, r);
            st[v] = merge(st[v * 2], st[v * 2 + 1]);
        }
        node query(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return {0, 0, 0, 0};
            if(l >= lo && r <= hi) return st[v];
            return merge(query(v * 2, l, (l + r) / 2, lo, hi),
                         query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
        }

		int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> s >> q; build(1, 0, n - 1);
            while(q--) {
                int l, r; cin >> l >> r; l--; r--;
                cout << query(1, 0, n - 1, l, r).ans << "\n";
            }
		}

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