Submission #108919

#	Time	Username	Problem	Language	Result	Execution time	Memory
108919		win11905	Election (BOI18_election)	C++11	100 / 100	2008 ms	44312 KiB

election

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define iii tuple<int, int, int>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 1<<19;

class election {
private:
    int n, m;
    int ans[N];
    char arr[N];
    vector<pii> que[N];
    int t[N<<1], lz[N<<1];
    void push(int p) {
        if(!lz[p]) return;
        t[p] += lz[p];
        if(p < N) lz[p<<1] += lz[p], lz[p<<1|1] += lz[p];
        lz[p] = 0;
    }
    template<typename T>
    void travel(int x, int y, const T &f, int p = 1, int l = 0, int r = N-1) {
        push(p);
        if(x > r || l > y || x > y) return;
        if(x <= l && r <= y) return f(p);
        int m = l + r >> 1;
        travel(x, y, f, p<<1, l, m), travel(x, y, f, p<<1|1, m+1, r);
        t[p] = min(t[p<<1], t[p<<1|1]);
    }
public:
    void solve(istream& cin, ostream& cout) {
        cin >> n;
        cin >> arr+1;
        cin >> m;
        for(int i = 0, l, r; i < m; ++i) {
            cin >> l >> r;
            que[r].emplace_back(l, i);
        }
        vector<int> stk;
        auto query = [&](int l, int r) {
            int mn = 1e9;
            travel(l, r, [&](int p) { mn = min(mn, t[p]); });
            return mn;
        };
        for(int i = 1; i <= n; ++i) {
            if(arr[i] == 'C') {
                if(!stk.empty()) {
                    travel(stk.back(), n, [&](int p) { lz[p]--, push(p); });
                    stk.pop_back();
                }
                travel(i, n, [&](int p) { lz[p]++, push(p); });
            } else stk.emplace_back(i);
            for(auto x : que[i]) {
                int z = query(x.x, i) - query(x.x-1, x.x-1);
                int pre = lower_bound(all(stk), x.x) - stk.begin();
                ans[x.y] = ((int)stk.size() - pre) - min(0, z);
            }
        }
        for(int i = 0; i < m; ++i) cout << ans[i] << endl;
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        election *obj = new election();
        obj->solve(in, out);
    }
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Compilation message (stderr)

election.cpp: In member function 'void election::solve(std::istream&, std::ostream&)':
election.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> arr+1;
                ~~~^~
election.cpp: In instantiation of 'void election::travel(int, int, const T&, int, int, int) [with T = election::solve(std::istream&, std::ostream&)::<lambda(int, int)>::<lambda(int)>]':
election.cpp:57:60:   required from here
election.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                 ~~^~~
election.cpp: In instantiation of 'void election::travel(int, int, const T&, int, int, int) [with T = election::solve(std::istream&, std::ostream&)::<lambda(int)>]':
election.cpp:63:75:   required from here
election.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
election.cpp: In instantiation of 'void election::travel(int, int, const T&, int, int, int) [with T = election::solve(std::istream&, std::ostream&)::<lambda(int)>]':
election.cpp:66:62:   required from here
election.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]

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