oj.uz

Submission #343500

# Submission time Handle Problem Language Result Execution time Memory
343500 2021-01-04T03:39:14 Z 12tqian Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1493 ms 57340 KB 
#include <bits/stdc++.h>

template<class T> struct Offline2DBIT { 
    bool mode = 0; // mode = 1 -> initialized
    int sz;
    std::vector<std::pair<int, int>> todo;
    std::vector<int> cnt, st, val;
    std::vector<T> bit;
    void init(int sz_) {
        sz = sz_;
        sz++;
        cnt.assign(sz, 0);
        st.assign(sz, 0);
        assert(!mode); mode = 1;
        std::vector<int> lst(sz, 0);
        cnt.assign(sz, 0);
        sort(todo.begin(), todo.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) { 
            return a.second < b.second; });
        for (auto& t : todo) 
            for (int x = t.first; x < sz; x += x & -x)
                if (lst[x] != t.second)
                    lst[x] = t.second, cnt[x]++;
        int sum = 0; 
        for (int i = 0; i < sz; i++)
            lst[i] = 0, st[i] = (sum += cnt[i]);
        val.resize(sum); bit.resize(sum);
        reverse(todo.begin(), todo.end());
        for (auto& t : todo) 
            for (int x = t.first; x < sz; x += x & -x)
                if (lst[x] != t.second)
                    lst[x] = t.second, val[--st[x]] = t.second;
    }
    int rank(int y, int l, int r) {
        return std::upper_bound(val.begin() + l, val.begin() + r, y) - val.begin() - l;
    }
    void inner_update(int x, int y, T t) {
        for (y = rank(y, st[x], st[x] + cnt[x]); y <= cnt[x]; y += y & -y)
            bit[st[x] + y - 1] += t;
    }
    void update(int x, int y, T t) {
        x++, y++;
        if (!mode) todo.push_back({x, y});
        else 
            for (; x < sz; x += x & -x)
                inner_update(x, y, t);
    }
    int inner_query(int x, int y) {
        T res = 0;
        for (y = rank(y, st[x], st[x] + cnt[x]); y; y -= y & -y)
            res += bit[st[x] + y - 1];
        return res;
    }
    T query(int x, int y) {
        x++, y++;
        assert(mode);
        T res = 0;
        for (; x; x -= x & -x) 
            res += inner_query(x, y);
        return res;
    }
    T query(int xl, int xr, int yl, int yr) {
        return query(xr, yr) - query(xl - 1, yr) - query(xr, yl - 1) + query(xl - 1, yl - 1);
    }
};

int main() { 
    using namespace std;
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    string s; cin >> s;
    set<pair<int, int>> ranges;
    int i1 = 0;
    int i2 = 0;
    while (i1 != n) {
        while (i2 != n - 1 && s[i2 + 1] == s[i1]) ++i2;
        if (s[i1] == '1') {
            ranges.emplace(i1, i2);
        }
        i1 = ++i2;
    }
    Offline2DBIT<long long> O;
    vector<vector<array<int, 3>>> changes(q + 1);
    vector<pair<int, int>> queries;
    queries.push_back({-1, -1});
    vector<int> add(q + 1);
    for (int i = 1; i <= q; i++) {
        string t; cin >> t;
        if (t == "toggle") {
            int id; cin >> id;
            id--;
            queries.emplace_back(id, -1);
            auto it = ranges.lower_bound({id + 1, -1});
            bool contained = false;
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->first <= id && id <= it->second) {
                    changes[i].push_back({it->first, it->second, i});
                    O.update(it->first, it->second, i);
                    int l1 = it->first;
                    int r1 = id - 1;
                    int l2 = id + 1;
                    int r2 = it->second;
                    if (l1 <= r1) {
                        changes[i].push_back({l1, r1, -i});
                        O.update(l1, r1, -i);
                        ranges.emplace(l1, r1);
                    }
                    if (l2 <= r2) {
                        changes[i].push_back({l2, r2, -i});
                        O.update(l2, r2, -i);
                        ranges.emplace(l2, r2);
                    }
                    ranges.erase({l1, r2});
                    contained = true;
                }
            }
            if (!contained) {
                pair<int, int> bef = {-1, -1};
                pair<int, int> aft = {-1, -1};
                pair<int, int> cur = {id, id};
                it = ranges.lower_bound({id, id});
                if (it != ranges.end() && it->first == id + 1) {
                    aft = *it;
                    changes[i].push_back({aft.first, aft.second, i});
                    O.update(aft.first, aft.second, i);
                    cur.second = aft.second;
                }
                if (it != ranges.begin() && prev(it)->second == id - 1) {
                    bef = *prev(it);
                    changes[i].push_back({bef.first, bef.second, i});
                    O.update(bef.first, bef.second, i);
                    cur.first = bef.first;
                }
                changes[i].push_back({cur.first, cur.second, -i});
                O.update(cur.first, cur.second, -i);
                ranges.emplace(cur.first, cur.second);
                if (bef.first != -1) {
                    ranges.erase(bef);
                }
                if (aft.first != -1) {
                    ranges.erase(aft);
                }
            }
        } else {
            int l, r; cin >> l >> r;
            r--;
            l--, r--;
            queries.emplace_back(l, r);
            auto it = ranges.lower_bound({l + 1, -1});
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->first <= l && r <= it->second) {
                    add[i] += i;
                }
            }
        }   
    }
    O.init(n);
    for (int i = 1; i <= q; i++) {
        if (queries[i].second == -1) {
            for (auto c : changes[i]) {
                O.update(c[0], c[1], c[2]);
            }
        } else {
            int l = queries[i].first;
            int r = queries[i].second;
            long long ans = O.query(0, l, r, n - 1) + add[i];
            cout << ans << '\n';
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 20180 KB Output is correct
2 Correct 306 ms 20160 KB Output is correct
3 Correct 441 ms 21184 KB Output is correct
4 Correct 974 ms 42432 KB Output is correct
5 Correct 992 ms 39200 KB Output is correct
6 Correct 1012 ms 46700 KB Output is correct
7 Correct 153 ms 15468 KB Output is correct
8 Correct 158 ms 16688 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1493 ms 55256 KB Output is correct
6 Correct 1284 ms 48476 KB Output is correct
7 Correct 948 ms 38504 KB Output is correct
8 Correct 157 ms 16748 KB Output is correct
9 Correct 102 ms 9956 KB Output is correct
10 Correct 112 ms 11876 KB Output is correct
11 Correct 113 ms 11896 KB Output is correct
12 Correct 156 ms 15340 KB Output is correct
13 Correct 158 ms 16752 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 358 ms 19564 KB Output is correct
6 Correct 727 ms 35100 KB Output is correct
7 Correct 1031 ms 46196 KB Output is correct
8 Correct 1399 ms 57340 KB Output is correct
9 Correct 335 ms 24648 KB Output is correct
10 Correct 303 ms 29128 KB Output is correct
11 Correct 332 ms 24648 KB Output is correct
12 Correct 308 ms 29124 KB Output is correct
13 Correct 334 ms 24784 KB Output is correct
14 Correct 316 ms 29252 KB Output is correct
15 Correct 151 ms 15340 KB Output is correct
16 Correct 156 ms 16676 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 248 ms 20180 KB Output is correct
9 Correct 306 ms 20160 KB Output is correct
10 Correct 441 ms 21184 KB Output is correct
11 Correct 974 ms 42432 KB Output is correct
12 Correct 992 ms 39200 KB Output is correct
13 Correct 1012 ms 46700 KB Output is correct
14 Correct 153 ms 15468 KB Output is correct
15 Correct 158 ms 16688 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 2 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1493 ms 55256 KB Output is correct
21 Correct 1284 ms 48476 KB Output is correct
22 Correct 948 ms 38504 KB Output is correct
23 Correct 157 ms 16748 KB Output is correct
24 Correct 102 ms 9956 KB Output is correct
25 Correct 112 ms 11876 KB Output is correct
26 Correct 113 ms 11896 KB Output is correct
27 Correct 156 ms 15340 KB Output is correct
28 Correct 158 ms 16752 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 2 ms 492 KB Output is correct
33 Correct 358 ms 19564 KB Output is correct
34 Correct 727 ms 35100 KB Output is correct
35 Correct 1031 ms 46196 KB Output is correct
36 Correct 1399 ms 57340 KB Output is correct
37 Correct 335 ms 24648 KB Output is correct
38 Correct 303 ms 29128 KB Output is correct
39 Correct 332 ms 24648 KB Output is correct
40 Correct 308 ms 29124 KB Output is correct
41 Correct 334 ms 24784 KB Output is correct
42 Correct 316 ms 29252 KB Output is correct
43 Correct 151 ms 15340 KB Output is correct
44 Correct 156 ms 16676 KB Output is correct
45 Correct 119 ms 13260 KB Output is correct
46 Correct 163 ms 13172 KB Output is correct
47 Correct 480 ms 22348 KB Output is correct
48 Correct 959 ms 42204 KB Output is correct
49 Correct 119 ms 12772 KB Output is correct
50 Correct 121 ms 12772 KB Output is correct
51 Correct 121 ms 12772 KB Output is correct
52 Correct 124 ms 12768 KB Output is correct
53 Correct 117 ms 12772 KB Output is correct
54 Correct 123 ms 12804 KB Output is correct