Submission #1232897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232897		faruk	Election (BOI18_election)	C++17	0 / 100	13 ms	576 KiB

election

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

struct node {
    int sum, min_val;
};
void merge_node(node &t, node &a, node &b) 
{
    t.sum = a.sum + b.sum;
    t.min_val = min(b.min_val, a.min_val + b.sum);
}

struct seggy{
    vector<node> t; int n;
    seggy(int N) : n(1<<(__lg(N) + 1)) {
        t.resize(2*n, {0, 0});
    }
    int get() {return t[1].min_val;}
    void upd(int idx, int n_val) {
        for (idx += n, t[idx].sum = n_val, t[idx].min_val = min(0, n_val), idx /= 2; idx > 0; idx /= 2)
            merge_node(t[idx], t[idx * 2], t[idx * 2 + 1]);
    }
};

const int BLOCK_SIZE = 3;

struct query {
    int l, r, id;
    query() {}
    query(int l, int r, int id) : l(l), r(r), id(id) {}

    bool operator<(const query& b) const {
        if (l / BLOCK_SIZE == b.l / BLOCK_SIZE)
            return r < b.r;
        return l/BLOCK_SIZE < b.l /BLOCK_SIZE;
    }
};

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

    int n;
    cin >> n;
    vector<int> arr(n + 1), pref(n + 1);
    string S;
    cin >> S;
    int OFFSET = n + 5;
    vector<vector<int> > idxs(n * 2 + 10);
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == 'C')
            arr[i + 1] = 1;
        else
            arr[i + 1] = -1;
        pref[i + 1] = arr[i + 1] + pref[i];
        idxs[pref[i + 1] + OFFSET].push_back(i + 1);
    }

    int q;
    /*q = 3;
    vector<query> queries = {
        {1, 6, 0},
        {3, 4, 1},
        {2, 6, 2}
    };*/
    
    cin >> q;
    vector<query> queries(q);
    for (int i = 0; i < q; i++)
    {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }
    sort(all(queries));

    int L = 1, R = 1;
    deque<int> imp;
    seggy seg(n + 1);
    if (arr[1] != -1)
        seg.upd(1, arr[1]);
    else
        imp.push_back(1);

    vector<int> out(n);
    for (auto [l, r, id] : queries) {
        while (l < L) { // move by one to the left
            seg.upd(L - 1, arr[L - 1]);
            // need to get new pref, L - 2 is new pref
            if (pref[L - 2] > pref[L - 1]) { // in this case we added a minus
                int searched = pref[L - 2] - 1 + OFFSET;
                int next_beg = lower_bound(all(idxs[searched]), L - 1) - idxs[searched].begin();
                if (next_beg < idxs[searched].size() and idxs[searched][next_beg] <= R) {
                    imp.push_front(idxs[searched][next_beg]);
                    seg.upd(idxs[searched][next_beg], 0);
                }
            } else {
                if (!imp.empty()) { // removing pref[L - 2] - 1, which is 
                    seg.upd(imp.front(), arr[imp.front()]);
                    imp.pop_front();
                }
            }
            L--;
        }
        while (r > R) {
            seg.upd(R + 1, arr[R + 1]);
            if ((!imp.empty() and pref[R + 1] == pref[imp.back()] - 1) || (imp.empty() and pref[R + 1] == pref[L - 1] - 1)) {
                seg.upd(R + 1, 0);
                imp.push_back(R + 1);
            }
            R++;
        }

        while (l > L) {
            seg.upd(L - 1, 0);
            if (!imp.empty() and imp.front() == L - 1)
                imp.pop_front();
            if (pref[L - 1] < pref[L]) { // novi je pref [L], tako da ovo znaci da smo izgubili + i eventualno dodajemo novi
                int searched = pref[L] - 1 + OFFSET;
                int next_beg = lower_bound(all(idxs[searched]), L + 1) - idxs[searched].begin();
                if (next_beg < idxs[searched].size() and idxs[searched][next_beg] <= R) {
                    imp.push_front(idxs[searched][next_beg]);
                    seg.upd(idxs[searched][next_beg], 0);
                }
            } else {
                if (!imp.empty() and pref[imp.front()] == pref[L - 1] - 1) {
                    seg.upd(imp.front(), arr[imp.front()]);
                    imp.pop_front();
                }
            }

            L++;
        }

        while (r < R) {
            seg.upd(R, 0);
            if (!imp.empty() and imp.back() == R)
                imp.pop_back();
            R--;
        }

        int val = imp.size() - min(0, seg.t[1].min_val);
        out[id] = val;
    }

    for (int i = 0; i < q; i++)
        cout << out[i] << "\n";
}
/*
11
CCCTTTTTTCC
3
1 11
4 9
2 6
*/

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