Submission #1064480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064480		MisterReaper	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	861 ms	67292 KiB

street_lamps

// File C.cpp created on 18.08.2024 at 15:17:15
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "../debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int maxN = 3E5 + 5;

int lsb(int x) {
    return x & -x;
}
struct fenwick {
    int n;
    std::vector<i64> tree;
    std::vector<std::pair<int, int>> his;
    fenwick(int _n) : n(_n), tree(n + 1) {}
    void modify(int p, int x, bool flag = true) {
        if(flag) his.emplace_back(p, x);
        for(p += 1; p <= n; p += lsb(p)) {
            tree[p] += x;
        }
    }
    i64 query(int p) {
        i64 res = 0;
        for(p += 1; p; p -= lsb(p)) {
            res += tree[p];
        }
        return res;
    }
    i64 query(int l, int r) {
        return query(r) - query(l - 1);
    }
    void roll() {
        while(!his.empty()) {
            modify(his.back().first, -his.back().second, false);
            his.pop_back();
        }
    }
} fen(maxN);

bool isq[maxN];
int N, Q, ans[maxN];
std::string S;
std::vector<std::array<int, 4>> segs;

void dnq(int l, int r) {
    if(l >= r) {
        return;
    }
    int mid = (l + r) >> 1;
    dnq(l, mid);
    dnq(mid + 1, r);

    debug(l, r);
    int ptr[2]{l, mid + 1};
    std::vector<std::array<int, 4>> tmp;
    while(ptr[0] <= mid && ptr[1] <= r) {
        if(segs[ptr[0]][2] <= segs[ptr[1]][2]) {
            tmp.push_back(segs[ptr[0]++]);
            if(tmp.back()[0] == 0) {
                debug(tmp.back()[3], tmp.back()[1]);
                fen.modify(tmp.back()[3], tmp.back()[1]);
            }
        } else {
            tmp.push_back(segs[ptr[1]++]);
            if(tmp.back()[0] == 1) {
                debug(tmp.back()[1], fen.query(tmp.back()[3], maxN - 1));
                ans[tmp.back()[1]] += fen.query(tmp.back()[3], maxN - 1);
            }
        }
    }
    while(ptr[0] <= mid) {
        tmp.push_back(segs[ptr[0]++]);
        if(tmp.back()[0] == 0) {
            debug(tmp.back()[3], tmp.back()[1]);
            fen.modify(tmp.back()[3], tmp.back()[1]);
        }
    }
    while(ptr[1] <= r) {
        tmp.push_back(segs[ptr[1]++]);
        if(tmp.back()[0] == 1) {
            debug(tmp.back()[1], fen.query(tmp.back()[3], maxN - 1));
            ans[tmp.back()[1]] += fen.query(tmp.back()[3], maxN - 1);
        }
    }

    debug(tmp);
    for(int i = l; i <= r; ++i) {
        segs[i] = tmp[i - l];
    }
    debug("wtf");
    fen.roll();
    debug("ok");
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> Q;
    std::cin >> S;
    S = "0" + S + "0";
    N += 2;

    std::set<int> cl;
    for(int i = 0, j = 0; i < N; i = j) {
        if(S[i] == '0') {
            ++j;
            cl.emplace(i);
        } else {
            while(j < N && S[j] == '1') ++j;
            segs.push_back({0, -1, i, j - 1});
        }
    }
    for(int i = 2; i <= Q + 1; ++i) {
        std::string T;
        std::cin >> T;
        if(T[0] == 'q') {
            isq[i] = true;
            int L, R;
            std::cin >> L >> R;
            --R;
            segs.push_back({1, i, L, R});
        } else {
            int X;
            std::cin >> X;
            if(S[X] == '1') {
                int nxt = *cl.lower_bound(X);
                int bef = *--cl.lower_bound(X);
                segs.push_back({0, +i, bef + 1, nxt - 1});
                segs.push_back({0, -i, bef + 1, X - 1});
                segs.push_back({0, -i, X + 1, nxt - 1});
                S[X] = '0';
                cl.emplace(X);
            } else {
                S[X] = '1';
                cl.erase(X);
                int nxt = *cl.lower_bound(X);
                int bef = *--cl.lower_bound(X);
                segs.push_back({0, +i, bef + 1, X - 1});
                segs.push_back({0, +i, X + 1, nxt - 1});
                segs.push_back({0, -i, bef + 1, nxt - 1});
            }
        }
    }

    debug(segs);
    dnq(0, int(segs.size()) - 1);

    for(int i = 0; i <= Q + 1; ++i) {
        if(isq[i]) {
            if(ans[i] < 0) ans[i] += i;
            std::cout << ans[i] << '\n';
        }
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20