Submission #672283

#	Time	Username	Problem	Language	Result	Execution time	Memory
672283		RaresFelix	Election (BOI18_election)	C++17	100 / 100	1181 ms	64060 KiB

election

#include <bits/stdc++.h>

using namespace std;
using ii = pair<int, int>;
const int MN = 500071;
int A[MN], Re[MN];
int n, q;
vector<ii> Q[MN];

stack<int> PozDez;

namespace AINT {
    int V[4 * MN], Lz[4 * MN], Pmin[4 * MN], Vmin[4 * MN];

    void init(int u = 1, int s = 1, int d = n) {
        V[u] = Lz[u] = Vmin[u] = 0;
        Pmin[u] = s;
        if(s != d) {
            init(u << 1, s, (s + d) >> 1);
            init(u << 1 | 1, ((s + d) >> 1) + 1, d);
        }
    }

    void prop(int u, int s, int d) {
        V[u] += Lz[u];
        Vmin[u] += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void add(int l, int r, int v, int u = 1, int s = 1, int d = n) {
        prop(u, s, d);
        if(d < l || r < s) {
            return;
        }
        if(l <= s && d <= r) {
            Lz[u] = v;
            prop(u, s, d);
            return;
        }
        add(l, r, v, u << 1, s, (s + d) >> 1);
        add(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        if(Vmin[u << 1] <= Vmin[u << 1 | 1]) {
            Vmin[u] = Vmin[u << 1];
            Pmin[u] = Pmin[u << 1];
        } else {
            Vmin[u] = Vmin[u << 1 | 1];
            Pmin[u] = Pmin[u << 1 | 1];
        }
    }

    int poz_neg() {
        if(Vmin[1] >= 0) return -1;
        assert(Vmin[1] == -1);
        return Pmin[1];
    }
}

namespace AINT2 {
    int V[4 * MN], SufMin[4 * MN];

    void update(int p, int v, int u = 1, int s = 1, int d = n) {
        if(d < p || p < s) return;
        if(s == d) {
            V[u] = v;
            SufMin[u] = min(0, v);
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = V[u << 1] + V[u << 1 | 1];
        SufMin[u] = min(SufMin[u << 1 | 1], SufMin[u << 1] + V[u << 1 | 1]);
    }
    pair<int, int> query(int l, int r, int u = 1, int s = 1, int d = n) { ///(sum, sufmin)
        if(d < l || r < s) return {0, 0};
        if(l <= s && d <= r) return {V[u], SufMin[u]};
        ii r1 = query(l, r, u << 1, s, (s + d) >> 1), r2 = query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
        return {r1.first + r2.first, min(r2.first + r1.second, r2.second)};
    }
}

namespace AIB {
    int V[MN];
    void update(int p, int v) {
        while(p < MN) {
            V[p] += v;
            p += p & -p;
        }
    }
    int f(int p) {
        int r = 0;
        while(p) {
            r += V[p];
            p -= p & -p;
        }
        return r;
    }
    int query(int l, int r) {
        if(!l) return f(r);
        return f(r) - f(l - 1);
    }
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        char c; cin >> c;
        A[i] = (c == 'C') ? 1 : -1;
    }
    cin >> q;
    for(int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        Q[l].push_back({r, i});
    }
    int nr_dez = 0;
    AINT::init();
    for(int i = n; i >= 1; --i) {
        ///adaugam i
        AINT::add(i, n, A[i]);
        AINT2::update(i, A[i]);
        if(A[i] == 1) {
            if(!PozDez.empty()) {
                int p1 = PozDez.top();
//                printf("L-am activat pe %d\n", p1);
                AIB::update(p1, -1);
                AINT::add(p1, n, -1);
                AINT2::update(p1, -1);
                PozDez.pop();
            }
        }
        else {
            int p = AINT::poz_neg();
            if(p != -1) {
                AINT::add(p, n, 1);
//                printf("L-am deazactivat pe %d\n", p);
                AIB::update(p, 1);
                AINT2::update(p, 0);
                PozDez.push(p);
            }
        }

        for(auto it : Q[i]) {
            int r = it.first, pre = it.second;
            Re[pre] = AIB::query(i, r) + max(0, -AINT2::query(i, r).second);
        }
    }

    for(int i = 1; i <= q; ++i)
        cout << Re[i] << "\n";
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:119:9: warning: unused variable 'nr_dez' [-Wunused-variable]
  119 |     int nr_dez = 0;
      |         ^~~~~~

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