Submission #1197504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197504		alterio	Take-out (POI13_usu)	C++20	0 / 100	638 ms	102844 KiB

usu

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 1e6 + 10;

int L[mxn], R[mxn], indL[mxn], indR[mxn], suml[mxn], sumr[mxn];

struct S {
    int ind;
};

bool operator < (S f, S s) {
    return L[f.ind] + R[f.ind] < L[s.ind] + R[s.ind];
}

string s;

struct SGT {
    vector<int> sumL, sumR, lzL, lzR;
    
    SGT(int sz) {
        sumL.resize(3 * sz);
        sumR.resize(3 * sz);
        lzL.resize(3 * sz);
        lzR.resize(3 * sz);
    }

    void build(int k, int l, int r) {
        if (l == r) {
            sumL[k] = suml[l];
            sumR[k] = sumr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(k * 2, l, mid);
        build(k * 2 + 1, mid + 1, r);
        sumL[k] = max(sumL[k * 2], sumL[k * 2 + 1]);
        sumR[k] = max(sumR[k * 2], sumR[k * 2 + 1]);
    }

    void push(int k, int l, int r) {
        if (lzL[k]) {
            sumL[k] -= lzL[k];
            if (l != r) {
                lzL[k * 2] += lzL[k];
                lzL[k * 2 + 1] += lzL[k];
            }
            lzL[k] = 0;
        }
        if (lzR[k]) {
            sumR[k] -= lzR[k];
            if (l != r) {
                lzR[k * 2] += lzR[k];
                lzR[k * 2 + 1] += lzR[k];
            }
            lzR[k] = 0;
        }
    }

    int getValL(int k, int l, int r, int i) {
        push(k, l, r);
        if (l > i || r < i) return 0;
        int mid = (l + r) / 2;
        if (l == r) return sumL[k];
        return max(getValL(k * 2, l, mid, i), getValL(k * 2 + 1, mid + 1, r, i));
    }

    int getValR(int k, int l, int r, int i) {
        push(k, l, r);
        if (l > i || r < i) return 0;
        int mid = (l + r) / 2;
        if (l == r) return sumR[k];
        return max(getValR(k * 2, l, mid, i), getValR(k * 2 + 1, mid + 1, r, i));
    }

    int getL(int k, int l, int r, int i, int val) {
        push(k, l, r);
        if (l > i || sumR[k] < val) return 0;
        int mid = (l + r) / 2;
        if (r <= i) {
            if (l == r) return l;
            if (sumR[k * 2 + 1] >= val) return getL(k * 2 + 1, mid + 1, r, i, val);
            return getL(k * 2, l, mid, i, val);
        }
        return max(getL(k * 2, l, mid, i, val), getL(k * 2 + 1, mid + 1, r, i, val));
    }

    int getR(int k, int l, int r, int i, int val) {
        push(k, l, r);
        if (r < i || sumL[k] < val) return mxn;
        int mid = (l + r) / 2;
        if (l >= i) {
            if (l == r) return l;
            if (sumL[k * 2] >= val) return getR(k * 2, l, mid, i, val);
            return getR(k * 2 + 1, mid + 1, r, i, val);
        }
        return min(getR(k * 2, l, mid, i, val), getR(k * 2 + 1, mid + 1, r, i, val));
    }

    void fill(int k, int l, int r, int i, int j, vector<int> &v) {
        push(k, l, r);
        if ((sumL[k] <= 0 && sumR[k] <= 0) || l > j || r < i) return;
        int mid = (l + r) / 2;
        if (i <= l && r <= j) {
            sumL[k] = sumR[k] = 0;
            if (l == r) {
                if (s[l] == 'b') v.push_back(l);
                return;
            }
            fill(k * 2, l, mid, i, j, v);
            fill(k * 2 + 1, mid + 1, r, i, j, v);
        }
        fill(k * 2, l, mid, i, j, v);
        fill(k * 2 + 1, mid + 1, r, i, j, v);
        sumL[k] = max(sumL[k * 2], sumL[k * 2 + 1]);
        sumR[k] = max(sumR[k * 2], sumR[k * 2 + 1]);
    }

    void updL(int k, int l, int r, int i, int v) {
        push(k, l, r);
        if (r < i) return;
        int mid = (l + r) / 2;
        if (l >= i) {
            lzL[k] += v;
            push(k, l, r);
            return;
        }
        updL(k * 2, l, mid, i, v);
        updL(k * 2 + 1, mid + 1, r, i, v);
    }

    void updR(int k, int l, int r, int i, int v) {
        push(k, l, r);
        if (l > i) return;
        int mid = (l + r) / 2;
        if (r <= i) {
            lzR[k] += v;
            push(k, l, r);
            return;
        }
        updR(k * 2, l, mid, i, v);
        updR(k * 2 + 1, mid + 1, r, i, v);
    }
} sgt(mxn);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    cin >> s;
    s = "." + s;
    int sum = 0;
    vector<int> pos;
    for (int i = 1; i <= n; i++) {
        sum += (s[i] == 'b');
        suml[i] = sum;
    }
    sum = 0;
    for (int i = n; i >= 1; i--) {
        sum += (s[i] == 'b');
        sumr[i] = sum;
    }
    sum = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'b') sum++;
        else {
            L[i] = sum;
            if (pos.size()) R[pos.back()] = sum;
            pos.push_back(i);
            sum = 0;
        }
    } 
    R[pos.back()] = sum;
    priority_queue<S> pq;
    for (int i = 0; i < pos.size(); i++) {
        indL[pos[i]] = (i > 0 ? pos[i - 1] : -1);
        indR[pos[i]] = (i < pos.size() - 1 ? pos[i + 1] : -1);
        pq.push({pos[i]});
    }
    sgt.build(1, 1, n);
    vector<vector<int>> ans;
    while (pq.size()) {
        int ind = pq.top().ind;
        int lt = indL[ind], rt = indR[ind];
        pq.pop();
        int val = sgt.getValR(1, 1, n, ind);
        int posL = sgt.getL(1, 1, n, ind, min(L[ind], k) + val);
        val = sgt.getValL(1, 1, n, posL - 1);
        int posR = sgt.getR(1, 1, n, posL, k + val);
        vector<int> elements = {ind};
        sgt.fill(1, 1, n, posL, posR, elements);
        sgt.updL(1, 1, n, posR, k);
        sgt.updR(1, 1, n, posL, k);
        sort(all(elements));
        ans.push_back(elements);
        if (1 <= lt && lt <= n) R[lt] = L[ind] + R[ind] - 1 - k, indR[lt] = rt;
        if (1 <= rt && rt <= n) L[rt] = L[ind] + R[ind] - 1 - k, indL[rt] = lt;
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        for (auto x : ans[i]) cout << x << " ";
        cout << endl;
    }
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 12