Submission #862335

#	Time	Username	Problem	Language	Result	Execution time	Memory
862335		Alcabel	Modern Machine (JOI23_ho_t5)	C++17	100 / 100	1416 ms	116500 KiB

Main

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

struct SegTree {
    int n, N, mod;
    vector<vector<pair<int, int>>> segs;
    vector<vector<int>> add;
    SegTree() {}
    SegTree(int _n, int _mod) {
        n = _n, mod = _mod;
        N = 1;
        while (N < n) {
            N <<= 1;
        }
        segs.resize(2 * N);
        add.resize(2 * N);
    }
    void build(int v, int tl, int tr, const vector<int>& a) {
        if (tl + 1 == tr) {
            if (tl < n) {
                segs[v] = {{0, a[tl] - 1}, {a[tl], mod - 1}};
                add[v] = {a[tl] + 1 < mod ? a[tl] + 1 : 0, a[tl]};
            } else {
                segs[v] = {{0, mod - 1}};
                add[v] = {0};
            }
            return;
        }
        int m = tl + (tr - tl) / 2;
        build(2 * v, tl, m, a);
        build(2 * v + 1, m, tr, a);
        for (int i = 0; i < (int)segs[2 * v].size(); ++i) {
            int l = segs[2 * v][i].first, r = segs[2 * v][i].second;
            int nxt = l + add[2 * v][i];
            if (nxt >= mod) { nxt -= mod; }
            int j = upper_bound(segs[2 * v + 1].begin(), segs[2 * v + 1].end(), make_pair(nxt, mod)) - segs[2 * v + 1].begin() - 1;
            while (segs[2 * v + 1][j].second - nxt < r - l) {
                segs[v].emplace_back(l, l + segs[2 * v + 1][j].second - nxt);
                add[v].emplace_back(add[2 * v][i] + add[2 * v + 1][j]);
                if (add[v].back() >= mod) {
                    add[v].back() -= mod;
                }
                l = segs[v].back().second + 1;
                nxt = l + add[2 * v][i];
                if (nxt >= mod) { nxt -= mod; }
                ++j;
                if (j == (int)segs[2 * v + 1].size()) {
                    j = 0;
                }
                assert(segs[2 * v + 1][j].first <= nxt && segs[2 * v + 1][j].second >= nxt);
            }
            segs[v].emplace_back(l, r);
            add[v].emplace_back(add[2 * v][i] + add[2 * v + 1][j]);
            if (add[v].back() >= mod) {
                add[v].back() -= mod;
            }
        }
    }
    void build(const vector<int>& a) {
        build(1, 0, N, a);
    }
    int query(int v, int tl, int tr, int l, int r, int rocks) {
        if (l <= tl && tr <= r) {
            int pos = upper_bound(segs[v].begin(), segs[v].end(), make_pair(rocks, mod)) - segs[v].begin() - 1;
            rocks += add[v][pos];
            if (rocks >= mod) { rocks -= mod; }
            return rocks;
        }
        int m = tl + (tr - tl) / 2;
        if (l < m) {
            rocks = query(2 * v, tl, m, l, r, rocks);
        }
        if (m < r) {
            rocks = query(2 * v + 1, m, tr, l, r, rocks);
        }
        return rocks;
    }
    int query(int l, int r, int rocks) {
        if (l >= r) { return rocks; }
        return query(1, 0, N, l, r, rocks);
    }
    ~SegTree() {}
};

const int maxlog = 17, maxn = 12e4 + 1;
long long prefLeq[maxn][maxlog], prefReq[maxn][maxlog], pref[maxn];
int cntReq[maxn][maxlog], Log[maxn];

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<int> posBPref, posRSuf;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'B') {
            posBPref.emplace_back(i);
        } else {
            posRSuf.emplace_back(i);
        }
    }
    reverse(posRSuf.begin(), posRSuf.end());
    posBPref.emplace_back(n);
    posRSuf.emplace_back(-1);
    vector<int> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        pref[i + 1] = pref[i] + a[i];
        for (int k = 0; k < maxlog; ++k) {
            prefLeq[i + 1][k] = prefLeq[i][k] + (a[i] <= (1 << k)) * a[i];
            prefReq[i + 1][k] = prefReq[i][k] + (a[i] > (n - (1 << k))) * a[i];
            cntReq[i + 1][k] = cntReq[i][k] + (a[i] > (n - (1 << k)));
        }
    }
    SegTree st(m, n + 1);
    st.build(a);
    auto makeStep = [&](int j, int& prefR, int& sufB, int& addPref, int& addSuf) -> void {
        int cntB = (int)posBPref.size() - 1 - addPref + addSuf;
        char type;
        if (j <= prefR) {
            type = 'R';
        } else if (j > n - sufB) {
            type = 'B';
        } else {
            type = s[j - 1];
        }
        if (type == 'B') {
            ++j;
        }
        if (cntB >= j) {
            // take j-th B
            addPref += j;
        } else {
            // take n + 1 - j -th R
            addSuf += n + 1 - j;
        }
        if (addPref >= (int)posBPref.size() || addSuf >= (int)posRSuf.size() || (posBPref[addPref] + n - posRSuf[addSuf] - 1 > n)) {
            if (cntB >= j) {
                // addPref -= j;
                int leftB = cntB - sufB;
                sufB -= (j - leftB);
                prefR = n - sufB;
            } else {
                // addSuf -= (n + 1 - j);
                int cntR = n - cntB;
                int rightR = cntR - prefR;
                prefR -= (n + 1 - j - rightR);
                sufB = n - prefR;
            }
            addPref = (int)posBPref.size() - 1, addSuf = (int)posRSuf.size() - 1;
        } else {
            prefR = posBPref[addPref], sufB = n - posRSuf[addSuf] - 1;
        }
        // cerr << "cntB: " << cntB << ", type: " << type << ", addPref: " << addPref << ", addSuf: " << addSuf << '\n';
        assert(prefR + sufB <= n);
    };
    auto collided = [&](int addPref, int addSuf) -> bool {
        addPref = min(addPref, (int)posBPref.size() - 1);
        addSuf = min(addSuf, (int)posRSuf.size() - 1);
        // cerr << "Rs: " << posBPref[addPref] << ", Bs: " << n - posRSuf[addSuf] - 1 << '\n';
        return posBPref[addPref] + n - posRSuf[addSuf] - 1 >= n;
    };
    auto willCollide = [&](int prefR, int sufB, int addPref, int addSuf, int l, int r) -> bool {
        int lgr = Log[prefR], lgb = Log[sufB];
        long long  newAddPref = (lgr != -1 ? addPref + prefLeq[r][lgr] - prefLeq[l][lgr] : addPref);
        long long newAddSuf = (lgb != -1 ? addSuf + n * 1ll * (cntReq[r][lgb] - cntReq[l][lgb]) - (prefReq[r][lgb] - prefReq[l][lgb]) : addSuf);
        if (newAddPref >= (int)posBPref.size() || newAddSuf >= (int)posRSuf.size()) {
            return true;
        }
        return collided(newAddPref, newAddSuf);
    };
    auto completeTillCollide = [&](int& prefR, int& sufB, int& addPref, int& addSuf, int l, int r) -> int {
        // collision is on [l, r) ?
        int lgr = Log[prefR], lgb = Log[sufB];
        int left = l, right = r + 1;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (willCollide(prefR, sufB, addPref, addSuf, l, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        // cerr << "left: " << left << '\n';
        if (lgr != -1) {
            addPref += prefLeq[left][lgr] - prefLeq[l][lgr];
        }
        if (lgb != -1) {
            addSuf += n * 1ll * (cntReq[left][lgb] - cntReq[l][lgb]) - (prefReq[left][lgb] - prefReq[l][lgb]);
        }
        prefR = posBPref[addPref], sufB = n - posRSuf[addSuf] - 1;
        // cerr << "prefR: " << prefR << ", sufB: " << sufB << ", addPref: " << addPref << ", addSuf: " << addSuf << ", l: " << l << ", r: " << r << '\n';
        if (left < r) {
            // collided
            makeStep(a[left], prefR, sufB, addPref, addSuf);
            return left + 1;
        }
        return left;
    };
    auto hasBad = [&](int prefR, int sufB, int l, int r) -> bool {
        int lgr = Log[prefR], lgb = Log[sufB];
        long long goodSum = 0;
        if (lgr != -1) {
            goodSum += prefLeq[r][lgr] - prefLeq[l][lgr];
        }
        if (lgb != -1) {
            goodSum += prefReq[r][lgb] - prefReq[l][lgb];
        }
        return goodSum < pref[r] - pref[l];
    };
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        int prefR = posBPref[0], sufB = n - posRSuf[0] - 1;
        int addPref = 0, addSuf = 0;
        if (prefR == 0 && sufB == 0) {
            makeStep(a[l], prefR, sufB, addPref, addSuf);
            ++l;
        }
        while (!collided(addPref, addSuf) && l < r) {
            // cerr << "!\n";
            int left = l, right = r + 1;
            while (right - left > 1) {
                int mid = left + (right - left) / 2;
                if (hasBad(prefR, sufB, l, mid)) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            // left is first bad
            l = completeTillCollide(prefR, sufB, addPref, addSuf, l, left);
            if (!collided(addPref, addSuf) && l < r) {
                makeStep(a[l], prefR, sufB, addPref, addSuf);
                ++l;
            }
        }
        int ans;
        // cerr << "prefR: " << prefR << ", sufB: " << sufB << ", addPref: " << addPref << ", addSuf: " << addSuf << ", l: " << l << ", r: " << r << '\n';
        if (collided(addPref, addSuf)) {
            ans = st.query(l, r, prefR);
        } else {
            // cerr << "prefR: " << prefR << ", sufB: " << sufB << ", addPref: " << addPref << ", addSuf: " << addSuf << ", l: " << l << ", r: " << r << '\n';
            ans = (int)posRSuf.size() - 1 + addPref - addSuf;
            // ans = cntRocks[n - sufB] - cntRocks[prefR] + prefR;
        }
        cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    Log[0] = -1, Log[1] = 0;
    for (int i = 2; i < maxn; ++i) {
        Log[i] = Log[i >> 1] + 1;
    }

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 12 / 12
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 26 / 26
• Subtask 6: 17 / 17
• Subtask 7: 21 / 21