제출 #172577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172577		rama_pang	가로등 (APIO19_street_lamps)	C++14	100 / 100	1785 ms	83948 KiB

street_lamps

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

template<typename Data>
struct FenwickTree { // Range Update Point Query
    int N;
    vector<Data> Tree;

    FenwickTree() { N = 0; Tree.clear(); }

    /* Standard Tree Updates */
    int resize(int n) {
        N = n;
        Tree.resize(N + 1);
    }

    void update_tree(int p, Data x) {
        for (int i = p; i <= N; i += i & -i) {
            Tree[i] += x;
        }
    }

    /* Range Update and Point Query */
    void update(int l, int r, Data x) {
        update_tree(l, x); // Update Prefix Difference
        update_tree(r + 1, -x); // Update Prefix Difference
    }

    Data query(int p) {
        Data res = 0;
        for (int i = p; i > 0; i -= i & -i) {
            res += Tree[i];
        }
        return res;
    }

};

template<typename Data>
struct FenwickTree2D { // 2D Range Update Point Query
// using Data = int;
    int N;
    vector<vector<int>> Coordinate;
    vector<FenwickTree<Data>> Tree;

    FenwickTree2D() { N = 0; Tree.clear(); }
    FenwickTree2D(int n) { N = n; resize(n); }

    /* Standard Tree Updates */
    void build() {
        for (int i = 1; i <= N; i++) {
            sort(begin(Coordinate[i]), end(Coordinate[i]));
            Coordinate[i].resize(unique(begin(Coordinate[i]), end(Coordinate[i])) - begin(Coordinate[i]));
            Tree[i].resize(Coordinate[i].size());
        }
    }

    int resize(int n) {
        N = n;
        Tree.resize(n + 1);
        Coordinate.resize(n + 1);
    }

    void insert_query_interval(int a, int b) {
        for (int i = a; i > 0; i -= i & -i) {
            Coordinate[i].emplace_back(b);
        }
    }

    void update_tree(int p, int l, int r, Data x) {
        for (int i = p; i <= N; i += i & -i) {
            int idx_l = lower_bound(begin(Coordinate[i]), end(Coordinate[i]), l) - begin(Coordinate[i]) + 1; // first element that is >= l
            int idx_r = prev(upper_bound(begin(Coordinate[i]), end(Coordinate[i]), r)) - begin(Coordinate[i]) + 1; // last element that is <= r
            Tree[i].update(idx_l, idx_r, x);
        }
    }

    /* Range Update and Point Query Functions */
    void update(int lo, int hi, int l, int r, Data x) { // Range update rectangle (lo...hi) * (l...r)
        update_tree(lo, l, r, x); // Update Prefix Difference
        update_tree(hi + 1, l, r, -x); // Update Prefix Difference
    }

    Data query(int r, int c) {
        Data res = 0;
        for (int i = r; i > 0; i -= i & -i) {
            int idx = prev(upper_bound(begin(Coordinate[i]), end(Coordinate[i]), c)) - begin(Coordinate[i]) + 1; // last element that is <= r
            res += Tree[i].query(idx);
        }
        return res;
    }

};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, q;
    string s;

    cin >> n >> q;
    cin >> s;

    set<int> lamps; // lamps that are off - allows us to get range of consecutive on lamps
    FenwickTree2D<int> BIT(n);

    lamps.emplace(0);
    lamps.emplace(n + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '0') {
            lamps.emplace(i);
        }
    }

    vector<tuple<string, int, int>> events;
    events.emplace_back("", 0, 0);

    for (int qi = 1; qi <= q; qi++) {
        string t;
        cin >> t;
        if (t == "toggle") {
            int i;
            cin >> i;
            events.emplace_back(t, i, 0);
        } else if (t == "query") {
            int a, b;
            cin >> a >> b;
            b--;
            events.emplace_back(t, a, b);
            BIT.insert_query_interval(a, b);
        }
    }

    BIT.build();

    for (int qi = 1; qi <= q; qi++) {
        string t;
        t = get<0>(events[qi]);

        if (t == "toggle") {
            int i;
            i = get<1>(events[qi]);
            if (lamps.count(i) == 0) { // the i-th lamp is on
                int l = *prev(lamps.lower_bound(i)) + 1;
                int r = *lamps.upper_bound(i) - 1;
                lamps.emplace(i); // turn off the lamp
                BIT.update(l, i, i, r, qi); // Add ending time (ans = End - Start)
            } else { // the i-th lamp is off
                int l = *prev(lamps.lower_bound(i)) + 1;
                int r = *lamps.upper_bound(i) - 1;
                lamps.erase(i); // turn on the lamp
                BIT.update(l, i, i, r, -qi); // Add start time (ans = End - Start)
            }
        } else if (t == "query") {
            int a, b;
            a = get<1>(events[qi]);
            b = get<2>(events[qi]);

            int l = *prev(lamps.upper_bound(a)) + 1;
            int r = *lamps.upper_bound(a) - 1;
            int ans = BIT.query(a, b) + ((l <= a && b <= r)? qi : 0); // Add current time if range doesn't have ending time yet

            cout << ans << "\n";
        }
    }

    return 0;
}

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

street_lamps.cpp: In member function 'int FenwickTree<Data>::resize(int)':
street_lamps.cpp:15:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
street_lamps.cpp: In member function 'int FenwickTree2D<Data>::resize(int)':
street_lamps.cpp:62:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^

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