Submission #1197544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197544		alterio	Take-out (POI13_usu)	C++20	44 / 100	1099 ms	105712 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 + 2;

vector<int> v;
int L[mxn], R[mxn], indL[mxn], indR[mxn], suml[mxn], sumr[mxn];

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;
            push(k * 2 + 1, mid + 1, r);
            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;
            push(k * 2, l, mid);
            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) {
        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);
            fill(k * 2 + 1, mid + 1, r, i, j);
        }
        fill(k * 2, l, mid, i, j);
        fill(k * 2 + 1, mid + 1, r, i, j);
        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);
        sumL[k] = max(sumL[k * 2], sumL[k * 2 + 1]);
    }

    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);
        sumR[k] = max(sumR[k * 2], sumR[k * 2 + 1]);
    }
} 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<pair<int, int>> 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({L[pos[i]] + R[pos[i]], pos[i]});
    }
    sgt.build(1, 1, n);
    vector<vector<int>> ans;
    bool done[mxn];
    memset(done, 0, sizeof(done));
    while (pq.size()) {
        int ind = pq.top().second;
        pq.pop();
        if (done[ind]) continue;
        done[ind] = 1;
        int lt = indL[ind], rt = indR[ind];
        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);
        v = {ind};
        sgt.fill(1, 1, n, posL, posR);
        sgt.updL(1, 1, n, posR, k);
        sgt.updR(1, 1, n, posL, k);
        sort(all(v));
        ans.push_back(v);
        if (v.size() != k + 1 || posL <= 0 || posR > n) {
            while (1) {
                ;
            }
        }
        if (1 <= lt && lt <= n) R[lt] = L[ind] + R[ind] - k, indR[lt] = rt, pq.push({L[lt] + R[lt], lt});
        if (1 <= rt && rt <= n) L[rt] = L[ind] + R[ind] - k, indL[rt] = lt, pq.push({L[rt] + R[rt], rt});
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        for (auto x : ans[i]) cout << x << " ";
        cout << endl;
    }
}

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