제출 #624844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624844		dutinmeow	가로등 (APIO19_street_lamps)	C++17	40 / 100	5072 ms	231000 KiB

street_lamps

#define NDEBUG

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

#pragma region debug
#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
    return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
    return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '[';

    if (v.size()) {
        os << *v.begin();

        for (auto i = ++v.begin(); i != v.end(); i++)
            os << ", " << (*i);
    }

    return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
    os << '[';

    if (d.size()) {
        os << *d.begin();

        for (auto i = ++d.begin(); i != d.end(); i++)
            os << ", " << (*i);
    }

    return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
    os << '[';

    if (s.size()) {
        int n = s.size();
        vector<T> v(n);

        for (int i = 0; i < n; i++) {
            v[i] = s.top();
            s.pop();
        }

        os << v[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            os << ", " << v[i];

        }
    }

    return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
    os << '[';

    if (q.size()) {
        int n = q.size();
        vector<T> v(n);

        for (int i = 0; i < n; i++) {
            v[i] = q.front();
            q.pop();
        }

        os << v[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            os << ", " << v[i];
        }
    }

    return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
    os << '[';

    if (N) {
        os << *a.begin();

        for (auto i = ++a.begin(); i != a.end(); i++)
            os << ", " << (*i);
    }

    return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
    os << '[';

    if (s.size()) {
        os << *s.begin();

        for (auto i = ++s.begin(); i != s.end(); i++)
            os << ", " << (*i);
    }

    return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
    os << '[';

    if (s.size()) {
        os << *s.begin();

        for (auto i = ++s.begin(); i != s.end(); i++)
            os << ", " << (*i);
    }

    return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
    os << '[';

    if (s.size()) {
        os << *s.begin();

        for (auto i = ++s.begin(); i != s.end(); i++)
            os << ", " << (*i);
    }

    return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
    os << '[';

    if (m.size()) {
        os << '(' << m.begin()->first << " : " << m.begin()->second << ')';

        for (auto i = ++m.begin(); i != m.end(); i++)
            os << ", " << '(' << i->first << " : " << i->second << ')';
    }

    return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const unordered_map<T1, T2> &m) {
    os << '[';

    if (m.size()) {
        os << '(' << m.begin()->first << " : " << m.begin()->second << ')';

        for (auto i = ++m.begin(); i != m.end(); i++)
            os << ", " << '(' << i->first << " : " << i->second << ')';
    }

    return os << ']';
}

#define dbg1(a)                                             \
          if ((#a)[0] == '\"') {                                  \
              if ((#a) == "\"_h1\"")                              \
                  cerr << "--------------------------------\n";   \
              else if ((#a) == "\"_h2\"")                         \
                  cerr << "================================\n";   \
              else if ((#a) == "\"_h3\"")                         \
                  cerr << "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡\n";   \
              else if ((#a) == "\"_h4\"")                         \
                  cerr << "################################\n";   \
              else                                                \
                  cerr << a;                                      \
          } else {                                                \
              cerr << #a << " = " << a << '\n';                   \
          }
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg8, dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif
#pragma endregion debug

template<class Base>
class Segtree : public Base {
    using T = typename Base::T;
    using Base::dval;
    using Base::merge;
    using Base::apply;

protected:
    size_t n;

    struct node {
        T v;
        int l, r;
        node() = default;
        node(T _v, int _l, int _r) : v(_v), l(_l), r(_r) {}
    };

    int root;
    vector<node> tree;

    size_t new_node() {
        tree.emplace_back(dval, -1, -1);
        return tree.size() - 1;
    }

private:
    void update(int i, T v, int t, int tl, int tr) {
        if (tl == tr) {
            apply(tree[t].v, v);
            return;
        }

        int tm = (tl + tr) / 2;

        if (i <= tm) {
            if (tree[t].l == -1)
                tree[t].l = new_node();

            update(i, v, tree[t].l, tl, tm);
        } else {
            if (tree[t].r == -1)
                tree[t].r = new_node();

            update(i, v, tree[t].r, tm + 1, tr);
        }

        tree[t].v = merge(tree[t].l == -1 ? dval : tree[tree[t].l].v, tree[t].r == -1 ? dval : tree[tree[t].r].v);
    }

    T query(int l, int r, int t, int tl, int tr) {
        if (r < tl || tr < l)
            return dval;

        if (l <= tl && tr <= r)
            return tree[t].v;

        int tm = (tl + tr) / 2;
        return merge(tree[t].l == -1 ? dval : query(l, r, tree[t].l, tl, tm), tree[t].r == -1 ? dval : query(l, r,
                     tree[t].r, tm + 1, tr));
    }

public:
    Segtree() = default;

    Segtree(size_t _n) {
        init(_n);
    }

    void init(size_t _n) {
        n = _n;
        root = new_node();
    }

    void reserve(size_t _n) {
        tree.reserve(_n);
    }

    void clear() {
        tree.clear();
    }

    void update(int i, T v) {
        update(i, v, root, 0, n - 1);
    }

    T query(int l, int r) {
        return query(l, r, root, 0, n - 1);
    }
};

struct stinfo {
    using T = int;
    const T dval = 0;
    void apply(T &a, T b) {
        a += b;
    }
    T merge(T a, T b) {
        return a + b;
    }
};

class Fentree {
    size_t n;
    vector<Segtree<stinfo>> tree;

public:
    Fentree() = default;

    Fentree(size_t _n) {
        init(_n);
    }

    void init(size_t _n) {
        n = _n;
        tree.resize(n + 1);

        for (int i = 1; i <= n; i++)
            tree[i].init(n);
    }

    void update(int i, int j, int v) {
        // dbg("_h2", "updated:\n", i, j, v);
        for (i++; i <= n; i += i & -i)
            tree[i].update(j, v);
    }

    int query(int i, int l, int r) {
        int ret = 0;

        for (i++; i; i -= i & -i)
            ret += tree[i].query(l, r);

        return ret;
    }

    int query(int i, int j, int l, int r) {
        return query(j, l, r) - query(i - 1, l, r);
    }
};

int main() {
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    set<int> off;
    Fentree bit(N + 1);

    for (int i = 0; i < N; i++) {
        if (S[i] == '0') {
            auto [it, b] = off.insert(i);
            int r = *it - 1;
            int l = (it == off.begin() ? 0 : *prev(it) + 1);
            // update [l, r] x [l, r]
            dbg("_h4", "square update\n", l, r, l, r);
            bit.update(l, l, Q);
            bit.update(r + 1, l, -Q);
            bit.update(l, r + 1, -Q);
            bit.update(r + 1, r + 1, Q);
        } else if (i == N - 1) {
            int r = N - 1;
            int l = (off.empty() ? 0 : *prev(off.end()) + 1);
            // update [l, r] x [l, r]
            dbg("_h4", "square update\n", l, r, l, r);
            bit.update(l, l, Q);
            bit.update(r + 1, l, -Q);
            bit.update(l, r + 1, -Q);
            bit.update(r + 1, r + 1, Q);
        }
    }

    //dbg(off);
    for (int q = 1; q <= Q; q++) {
        string t;
        cin >> t;

        if (t == "query") {
            int l, r;
            cin >> l >> r;
            l--, r -= 2;

            if (off.lower_bound(l) == off.upper_bound(r)) {
                dbg("_h4", "query v1:\n", l, r, bit.query(0, l, 0, r), q);
                cout << bit.query(0, l, 0, r) - (Q - q) << '\n';
            } else {
                dbg("_h4", "query v2:\n", l, r, bit.query(0, l, 0, r), q);
                cout << bit.query(0, l, 0, r) << '\n';
            }
        } else if (t == "toggle") {
            int k;
            cin >> k;
            k--;

            if (S[k] == '0') {
                S[k] = '1';
                off.erase(k);
                auto itl = off.lower_bound(k);
                int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
                auto itr = off.upper_bound(k);
                int r = (itr == off.end() ? N - 1 : *itr - 1);
                // update [l, k] x [k, r]
                dbg("_h4", "square update\n", l, k, k, r, Q - q);
                bit.update(l, k, Q - q);
                bit.update(l, r + 1, q - Q);
                bit.update(k + 1, k, q - Q);
                bit.update(k + 1, r + 1, Q - q);
            } else {
                S[k] = '0';
                auto itl = off.lower_bound(k);
                int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
                auto itr = off.upper_bound(k);
                int r = (itr == off.end() ? N - 1 : *itr - 1);
                off.insert(k);
                // update [l, k] x [k, r]
                bit.update(l, k, q - Q);
                bit.update(l, r + 1, Q - q);
                bit.update(k + 1, k, Q - q);
                bit.update(k + 1, r + 1, q - Q);
            }
        }
    }
}

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

street_lamps.cpp:6: warning: ignoring '#pragma region debug' [-Wunknown-pragmas]
    6 | #pragma region debug
      | 
street_lamps.cpp:209: warning: ignoring '#pragma endregion debug' [-Wunknown-pragmas]
  209 | #pragma endregion debug
      | 
street_lamps.cpp: In member function 'void Fentree::init(size_t)':
street_lamps.cpp:327:27: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  327 |         for (int i = 1; i <= n; i++)
      |                         ~~^~~~
street_lamps.cpp: In member function 'void Fentree::update(int, int, int)':
street_lamps.cpp:333:21: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  333 |         for (i++; i <= n; i += i & -i)
      |                   ~~^~~~

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