제출 #1318242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318242		MisterReaper	가로등 (APIO19_street_lamps)	C++17	20 / 100	1910 ms	87436 KiB

street_lamps

// File C.cpp created on 01.02.2026 at 20:34:07
#include <bits/stdc++.h>

using i64 = long long;

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

template<typename T>
struct fenwick {
    std::vector<std::pair<int, T>> stk;
    int n;
    std::vector<T> tree;
    fenwick(int n_) : n(n_), tree(n + 1) {}
    void modify(int p, T x, bool flag = true) {
        if (flag) {
            stk.emplace_back(p, x);
        }
        for (p += 1; p <= n; p += p & -p) {
            tree[p] += x;
        }
    }
    void modify(int l, int r, T x, bool flag = true) {
        modify(l, x, flag);
        modify(r + 1, -x, flag);
    }
    T get(int p) {
        T res = 0;
        for (p += 1; p; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
    T get(int l, int r) {
        return get(r) - get(l - 1);
    }
    int snap() {
        return int(stk.size());
    }
    void roll(int tim) {
        while (snap() != tim) {
            modify(stk.back().first, -stk.back().second, false);
            stk.pop_back();
        }
    }
};

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

    int N, Q;
    std::cin >> N >> Q;

    std::string S;
    std::cin >> S;

    S = "0" + S + "0";
    N += 2;

    std::set<int> bad;

    std::vector<std::array<int, 5>> qrys;
    for (int i = 0, j = 0; i < N; i = j) {
        if (S[i] == '0') {
            j += 1;
            bad.emplace(i);
        } else {
            while (S[j + 1] == '1') {
                j += 1;
            }
            qrys.push_back({0, i, j, 0, +1});
            j += 1;
        }
    }

    std::vector<std::array<i64, 3>> ans;

    for (int j = 1; j <= Q; ++j) {
        std::string s;
        std::cin >> s;
        if (s[0] == 't') {
            int i;
            std::cin >> i;
            if (S[i] == '0') {
                bad.erase(i);
                int l = *--bad.lower_bound(i);
                int r = *bad.lower_bound(i);
                qrys.push_back({j, l + 1, i - 1, 0, -1});
                qrys.push_back({j, i + 1, r - 1, 0, -1});
                qrys.push_back({j, l + 1, r - 1, 0, +1});
                S[i] = '1';
            } else {
                int l = *--bad.lower_bound(i);
                int r = *bad.lower_bound(i);
                qrys.push_back({j, l + 1, i - 1, 0, +1});
                qrys.push_back({j, i + 1, r - 1, 0, +1});
                qrys.push_back({j, l + 1, r - 1, 0, -1});
                bad.emplace(i);
                S[i] = '0';
            }
        } else {
            int l, r;
            std::cin >> l >> r;
            --r;
            qrys.push_back({j, l, r, 1, ans.size()});
            ans.push_back({0, 0, j});
        }
    }

    debug(qrys);

    fenwick<int> fen1(N + 1);
    fenwick<i64> fen2(N + 1);

    auto aux = qrys;

    auto dfs = [&](auto&& self, int l, int r) -> void {
        if (l + 1 == r) {
            return;
        }
        int mid = (l + r) >> 1;
        self(self, l, mid);
        self(self, mid, r);
        int ptr0 = l;
        int ptr1 = mid;
        int snp1 = fen1.snap();
        int snp2 = fen2.snap();
        int ptr = l;
        while (ptr0 != mid && ptr1 != r) {
            if (qrys[ptr0][1] <= qrys[ptr1][1]) {
                if (qrys[ptr0][3] == 0) {
                    fen1.modify(0, qrys[ptr0][2], qrys[ptr0][4]);
                    fen2.modify(0, qrys[ptr0][2], qrys[ptr0][4] * qrys[ptr0][0]);
                } else {
                    // ok
                }
                aux[ptr++] = qrys[ptr0++];
            } else {
                if (qrys[ptr1][3] == 0) {
                    // ok
                } else {
                    ans[qrys[ptr1][4]][0] += fen1.get(qrys[ptr1][2]);
                    ans[qrys[ptr1][4]][1] += fen2.get(qrys[ptr1][2]);
                }
                aux[ptr++] = qrys[ptr1++];
            }
        }
        while (ptr0 != mid) {
            if (qrys[ptr0][3] == 0) {
                fen1.modify(0, qrys[ptr0][2], qrys[ptr0][4]);
                fen2.modify(0, qrys[ptr0][2], qrys[ptr0][4] * qrys[ptr0][0]);
            } else {
                // ok
            }
            aux[ptr++] = qrys[ptr0++];
        }
        while (ptr1 != r) {
            if (qrys[ptr1][3] == 0) {
                // ok
            } else {
                ans[qrys[ptr1][4]][0] += fen1.get(qrys[ptr1][2]);
                ans[qrys[ptr1][4]][1] += fen2.get(qrys[ptr1][2]);
            }
            aux[ptr++] = qrys[ptr1++];
        }
        for (int i = l; i < r; ++i) {
            qrys[i] = aux[i];
        }
        fen1.roll(snp1);
        fen2.roll(snp2);
    };
    dfs(dfs, 0, int(qrys.size()));

    for (int i = 0; i < int(ans.size()); ++i) {
        i64 res = 0;
        if (ans[i][0] == 1) {
            res = ans[i][2] - ans[i][1];
        } else {
            res = ans[i][1];
        }
        debug(ans[i]);
        std::cout << res << '\n';
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:109:49: warning: narrowing conversion of 'ans.std::vector<std::array<long long int, 3> >::size()' from 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  109 |             qrys.push_back({j, l, r, 1, ans.size()});
      |                                         ~~~~~~~~^~

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