oj.uz

답안 #374451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374451 2021-03-07T09:58:35 Z KoD 가로등 (APIO19_street_lamps) C++17
100 / 100
 2722 ms 125928 KB 
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct Fenwick {
    Vec<int> data;
    Fenwick() = default;
    Fenwick(const int n): data(n + 1) { }
    void add(int i, const int x) {
        for (i += 1; i < (int) data.size(); i += i & -i) {
            data[i] += x;
        }   
    }
    int get(int i) const {
        int ret = 0;
        for (i += 1; i > 0; i -= i & -i) {
            ret += data[i];
        }
        return ret;
    }
};

struct Add2D {
    Vec<Vec<int>> pts;
    Vec<Fenwick> fen;
    Add2D(const Vec<int> &x, const Vec<int> &y, const int n) {
        pts.resize(2 * n);
        fen.resize(2 * n);
        for (int i = 0; i < (int) x.size(); ++i) {
            pts[x[i] + n].push_back(y[i]);
        }
        for (int i = n; i < 2 * n; ++i) {
            std::sort(pts[i].begin(), pts[i].end());
            fen[i] = Fenwick(pts[i].size());
        }
        for (int i = n - 1; i > 0; --i) {
            pts[i].reserve(pts[i * 2].size() + pts[i * 2 + 1].size());
            std::copy(pts[i * 2].begin(), pts[i * 2].end(), std::back_inserter(pts[i]));
            std::copy(pts[i * 2 + 1].begin(), pts[i * 2 + 1].end(), std::back_inserter(pts[i]));
            std::inplace_merge(pts[i].begin(), pts[i].begin() + pts[i * 2].size(), pts[i].end());
            fen[i] = Fenwick(pts[i].size());
        }
    }
    void add(int l, int r, const int d, const int u, const int v) {
        for (l += size(), r += size(); l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                fen[l].add(std::lower_bound(pts[l].begin(), pts[l].end(), d) - pts[l].begin(), v);
                fen[l].add(std::lower_bound(pts[l].begin(), pts[l].end(), u) - pts[l].begin(), -v);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                fen[r].add(std::lower_bound(pts[r].begin(), pts[r].end(), d) - pts[r].begin(), v);
                fen[r].add(std::lower_bound(pts[r].begin(), pts[r].end(), u) - pts[r].begin(), -v);
            }
        }
    }
    int get(int x, const int y) const {
        int ret = 0;
        for (x += size(); x > 0; x >>= 1) {
            ret += fen[x].get(std::lower_bound(pts[x].begin(), pts[x].end(), y) - pts[x].begin());
        }
        return ret;
    }
    int size() const {
        return (int) pts.size() / 2;
    }
};  

int main() {
    int N, Q;
    std::cin >> N >> Q;
    Vec<int> state(N);
    for (auto &x: state) {
        char c;
        std::cin >> c;
        x = (c == '1');
    }
    std::set<int> off;
    for (int i = 0; i < N; ++i) {
        if (!state[i]) {
            off.insert(i);
        }
    }
    Vec<int> ans, X, Y;
    Vec<std::tuple<int, int, int, int, int>> add;
    Vec<std::pair<int, int>> qs;
    qs.reserve(Q);
    for (int t = 1; t <= Q; ++t) {
        std::string type;
        std::cin >> type;
        if (type == "query") {
            const auto idx = (int) ans.size();
            int a, b;
            std::cin >> a >> b;
            a -= 1;
            b -= 1;
            const auto itr = off.lower_bound(a);
            ans.push_back((itr == off.end() || *itr >= b) ? t : 0);
            X.push_back(a);
            Y.push_back(b);
            qs.emplace_back(idx, true);
        }
        else {
            const auto idx = (int) add.size();
            int s;
            std::cin >> s;
            s -= 1;
            if (off.find(s) == off.end()) {
                off.insert(s);
                const auto itr = off.find(s);
                const auto l = (itr == off.begin() ? 0 : *std::prev(itr) + 1);
                const auto r = (std::next(itr) == off.end() ? N : *std::next(itr));
                add.emplace_back(l, s, s + 1, r, t);
            }
            else {
                const auto itr = off.find(s);
                const auto l = (itr == off.begin() ? 0 : *std::prev(itr) + 1);
                const auto r = (std::next(itr) == off.end() ? N : *std::next(itr));
                add.emplace_back(l, s, s + 1, r, -t);
                off.erase(itr);
            }
            qs.emplace_back(idx, false);
        }
    }
    Add2D rect(X, Y, N + 1);
    for (const auto [i, f]: qs) {
        if (f) {
            ans[i] += rect.get(X[i], Y[i]);
        }
        else {
            const auto [l, r, d, u, v] = add[i];
            rect.add(l, r + 1, d, u + 1, v);
        }
    }
    for (const auto x: ans) {
        std::cout << x << '\n';
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 446 ms 20224 KB Output is correct
2 Correct 577 ms 23628 KB Output is correct
3 Correct 880 ms 29724 KB Output is correct
4 Correct 1402 ms 96900 KB Output is correct
5 Correct 1667 ms 94792 KB Output is correct
6 Correct 1250 ms 91740 KB Output is correct
7 Correct 2722 ms 125928 KB Output is correct
8 Correct 2400 ms 113236 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 715 ms 61936 KB Output is correct
6 Correct 1134 ms 78836 KB Output is correct
7 Correct 1552 ms 93160 KB Output is correct
8 Correct 2233 ms 112316 KB Output is correct
9 Correct 513 ms 23556 KB Output is correct
10 Correct 582 ms 25360 KB Output is correct
11 Correct 632 ms 26524 KB Output is correct
12 Correct 2470 ms 124940 KB Output is correct
13 Correct 2260 ms 112088 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2486 ms 117240 KB Output is correct
6 Correct 1841 ms 104704 KB Output is correct
7 Correct 1233 ms 90488 KB Output is correct
8 Correct 635 ms 69084 KB Output is correct
9 Correct 446 ms 18076 KB Output is correct
10 Correct 256 ms 15640 KB Output is correct
11 Correct 425 ms 17976 KB Output is correct
12 Correct 251 ms 15572 KB Output is correct
13 Correct 462 ms 17896 KB Output is correct
14 Correct 270 ms 15444 KB Output is correct
15 Correct 2629 ms 124628 KB Output is correct
16 Correct 2371 ms 112040 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 446 ms 20224 KB Output is correct
9 Correct 577 ms 23628 KB Output is correct
10 Correct 880 ms 29724 KB Output is correct
11 Correct 1402 ms 96900 KB Output is correct
12 Correct 1667 ms 94792 KB Output is correct
13 Correct 1250 ms 91740 KB Output is correct
14 Correct 2722 ms 125928 KB Output is correct
15 Correct 2400 ms 113236 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 2 ms 620 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 4 ms 620 KB Output is correct
20 Correct 715 ms 61936 KB Output is correct
21 Correct 1134 ms 78836 KB Output is correct
22 Correct 1552 ms 93160 KB Output is correct
23 Correct 2233 ms 112316 KB Output is correct
24 Correct 513 ms 23556 KB Output is correct
25 Correct 582 ms 25360 KB Output is correct
26 Correct 632 ms 26524 KB Output is correct
27 Correct 2470 ms 124940 KB Output is correct
28 Correct 2260 ms 112088 KB Output is correct
29 Correct 3 ms 620 KB Output is correct
30 Correct 3 ms 620 KB Output is correct
31 Correct 2 ms 620 KB Output is correct
32 Correct 2 ms 492 KB Output is correct
33 Correct 2486 ms 117240 KB Output is correct
34 Correct 1841 ms 104704 KB Output is correct
35 Correct 1233 ms 90488 KB Output is correct
36 Correct 635 ms 69084 KB Output is correct
37 Correct 446 ms 18076 KB Output is correct
38 Correct 256 ms 15640 KB Output is correct
39 Correct 425 ms 17976 KB Output is correct
40 Correct 251 ms 15572 KB Output is correct
41 Correct 462 ms 17896 KB Output is correct
42 Correct 270 ms 15444 KB Output is correct
43 Correct 2629 ms 124628 KB Output is correct
44 Correct 2371 ms 112040 KB Output is correct
45 Correct 210 ms 11056 KB Output is correct
46 Correct 336 ms 13776 KB Output is correct
47 Correct 735 ms 42112 KB Output is correct
48 Correct 1414 ms 95552 KB Output is correct
49 Correct 706 ms 28404 KB Output is correct
50 Correct 695 ms 28072 KB Output is correct
51 Correct 693 ms 29808 KB Output is correct
52 Correct 702 ms 35036 KB Output is correct
53 Correct 678 ms 34864 KB Output is correct
54 Correct 679 ms 34844 KB Output is correct