Submission #565804

#	Time	Username	Problem	Language	Result	Execution time	Memory
565804		shrimb	Election (BOI18_election)	C++17	0 / 100	21 ms	3540 KiB

election

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 200001;
const int sq = sqrt(maxn) + 1;

// {query index, left, right}

array<int,3> Q[maxn];
int ans[maxn], pl[maxn], pr[maxn];
bitset<maxn> active;

bool cmp (array<int,3> a, array<int,3> b) {
    a[0] /= sq;
    b[0] /= sq;
    return a < b;
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    string s;
    cin >> n >> s >> q;

    for (int i = 0 ; i < q ; i++) {
        int l, r;
        cin >> l >> r;
        l--,r--;
        Q[i] = {l, r, i};
    }
    sort(Q, Q + q, cmp);

    set<int> TL, TR, CL, CR;
    int CNT = 0;
    // CL: C empty from the Left
    // CR: C empty from the right
    // TL: T that needs Left
    memset(pl, -1, sizeof pl);
    memset(pr, -1, sizeof pr);

    auto activate = [&](int x) {
        if (!active[x]) active[x] = 1, CNT++;
    };
    auto deactivate = [&](int x) {
        if (!TL.count(x) and !TR.count(x)) active[x] = 0, CNT--;
    };
    int l = 0, r = -1;
    for (int i = 0 ; i < q ; i++) {
        auto [nl, nr, id] = Q[i];
        while (r < nr) {
            r++;
            if (s[r] == 'T') {
                if (CR.size()) {
                    pl[r] = *--CR.end();
                    CR.erase(--CR.end());
                } else TL.insert(r), activate(r);
                TR.insert(r), activate(r);
            } else {
                if (TR.size()) {
                    pl[r] = *TR.begin();
                    TR.erase(TR.begin());
                    deactivate(pl[r]);
                } else {
                    CL.insert(r);
                }
                CR.insert(r);
            }
        }
        while (l > nl) {
            l--;
            if (s[l] == 'T') {
                if (CL.size()) {
                    pr[l] = *CL.begin();
                    CL.erase(CL.begin());
                } else TR.insert(l), activate(l);
                TL.insert(l), activate(l);
            } else {
                if (TL.size()) {
                    pr[r] = *--TL.end();
                    TL.erase(--TL.end());
                    deactivate(pr[r]);
                } else {
                    CR.insert(l);
                }
                CL.insert(l);
            }
        }
        while (r > nr) {
            if (s[r] == 'T') {
                if (pl[r] != -1) {
                    auto it = TL.lower_bound(pl[r]);
                    if (it != TL.end()) {
                        pl[*it] = pl[r];
                        pr[pl[r]] = *it;
                        TL.erase(it);
                        deactivate(pr[pl[r]]);
                    }
                    pl[r] = -1;
                } else TL.erase(r), deactivate(r);
                TR.erase(r), deactivate(r);
            } else {
                if (pl[r] != -1) {
                    auto it = CL.lower_bound(pl[r]);
                    if (it != CL.end()) {
                        pl[*it] = pl[r];
                        pr[pl[r]] = *it;
                        CL.erase(it);
                    }
                    pl[r] = -1;
                } else CL.erase(r);
                CR.erase(r);
            }
            r--;
        }
        while (l < nl) {
            if (s[l] == 'T') {
                if (pr[l] != -1) {
                    auto it = TR.lower_bound(pr[l]);
                    if (it != TR.end()) {
                        pr[*it] = pr[l];
                        pl[pr[l]] = *it;
                        TR.erase(it);
                        deactivate(pl[pr[l]]);
                    }
                    pr[l] = -1;
                } else TR.erase(l), deactivate(l);
                TL.erase(l), deactivate(l);
            } else {
                if (pr[l] != -1) {
                    auto it = CR.lower_bound(pr[l]);
                    if (it != CR.end()) {
                        pr[*it] = pr[l];
                        pl[pr[l]] = *it;
                        CR.erase(it);
                    }
                    pr[l] = -1;
                } else CR.erase(l);
                CL.erase(l);
            }
            l++;
        }
        ans[id] = CNT;
    }
    for (int i  =0 ; i < q ; i++) cout << ans[i] << endl;
}

Compilation message (stderr)

election.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

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