oj.uz

Submission #343498

# Submission time Handle Problem Language Result Execution time Memory
343498 2021-01-04T03:25:43 Z 12tqian Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1498 ms 57312 KB 
#include <bits/stdc++.h>
using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<ll> vl;


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_;
        cnt.assign(sz, 0);
        st.assign(sz, 0);
    }
    void build() { 
        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) {
        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) {
        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() { 
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    string s; cin >> s;
    set<pi> 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+1, i2+1);
        }
        i1 = ++i2;
    }
    Offline2DBIT<ll> O;
    O.init(n + 5);
    vector<vector<array<int, 3>>> changes(q + 5);
    vpi queries;
    queries.pb({-1, -1});
    vi add(q + 1);
    f1r(i, 1, q + 1) {
        string t; cin >> t;
        if (t == "toggle") {
            int id; cin >> id;
            queries.eb(id, -1);
            auto it = ranges.lower_bound({id + 1, -1});
            bool contained = false;
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->f <= id && id <= it->s) {
                    changes[i].pb({it->f, it->s, i});
                    O.update(it->f, it->s, i);
                    int l1 = it->f;
                    int r1 = id-1;
                    int l2 = id+1;
                    int r2 = it->s;
                    if (l1 <= r1) {
                        changes[i].pb({l1, r1, -i});
                        O.update(l1, r1, -i);
                        ranges.emplace(l1, r1);
                    }
                    if (l2 <= r2) {
                        changes[i].pb({l2, r2, -i});
                        O.update(l2, r2, -i);
                        ranges.emplace(l2, r2);
                    }
                    ranges.erase({l1, r2});
                    contained = true;
                }
            }
            if (!contained) {
                pi bef = {-1, -1};
                pi aft = {-1, -1};
                pi cur = {id, id};
                it = ranges.lower_bound({id, id});
                if (it != ranges.end() && it->f == id + 1) {
                    aft = *it;
                    changes[i].pb({aft.f, aft.s, i});
                    O.update(aft.f, aft.s, i);
                    cur.s = aft.s;
                }
                if (it != ranges.begin() && prev(it)->s == id - 1) {
                    bef = *prev(it);
                    changes[i].pb({bef.f, bef.s, i});
                    O.update(bef.f, bef.s, i);
                    cur.f = bef.f;
                }
                changes[i].pb({cur.f, cur.s, -i});
                O.update(cur.f, cur.s, -i);
                ranges.emplace(cur.f, cur.s);
                if (bef.f != -1) {
                    ranges.erase(bef);
                }
                if (aft.f != -1) {
                    ranges.erase(aft);
                }
            }
        } else {
            int l, r; cin >> l >> r;
            r--;
            queries.eb(l, r);
            auto it = ranges.lower_bound({l + 1, -1});
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->f <= l && r <= it->s) {
                    add[i] += i;
                }
            }
        }   
    }
    O.build();
    f1r(i, 1, q+1) {
        if (queries[i].s == -1) {
            for (auto c : changes[i]) {
                O.update(c[0], c[1], c[2]);
            }
        } else {
            int l = queries[i].f;
            int r = queries[i].s;
            ll ans = O.query(1, l, r, n) + add[i];
            cout << ans << '\n';
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 364 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 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 251 ms 20032 KB Output is correct
2 Correct 302 ms 20160 KB Output is correct
3 Correct 465 ms 21144 KB Output is correct
4 Correct 1000 ms 42580 KB Output is correct
5 Correct 1057 ms 39308 KB Output is correct
6 Correct 1057 ms 46720 KB Output is correct
7 Correct 159 ms 15604 KB Output is correct
8 Correct 162 ms 16876 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 1498 ms 55132 KB Output is correct
6 Correct 1301 ms 48636 KB Output is correct
7 Correct 1006 ms 38484 KB Output is correct
8 Correct 161 ms 16876 KB Output is correct
9 Correct 105 ms 9952 KB Output is correct
10 Correct 115 ms 11876 KB Output is correct
11 Correct 114 ms 11872 KB Output is correct
12 Correct 163 ms 15604 KB Output is correct
13 Correct 159 ms 16748 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 2 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 389 ms 19564 KB Output is correct
6 Correct 755 ms 34736 KB Output is correct
7 Correct 1049 ms 46216 KB Output is correct
8 Correct 1404 ms 57312 KB Output is correct
9 Correct 340 ms 24648 KB Output is correct
10 Correct 324 ms 29128 KB Output is correct
11 Correct 333 ms 24648 KB Output is correct
12 Correct 327 ms 29128 KB Output is correct
13 Correct 336 ms 24776 KB Output is correct
14 Correct 317 ms 29124 KB Output is correct
15 Correct 159 ms 15604 KB Output is correct
16 Correct 158 ms 16876 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 364 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 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 251 ms 20032 KB Output is correct
9 Correct 302 ms 20160 KB Output is correct
10 Correct 465 ms 21144 KB Output is correct
11 Correct 1000 ms 42580 KB Output is correct
12 Correct 1057 ms 39308 KB Output is correct
13 Correct 1057 ms 46720 KB Output is correct
14 Correct 159 ms 15604 KB Output is correct
15 Correct 162 ms 16876 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 1498 ms 55132 KB Output is correct
21 Correct 1301 ms 48636 KB Output is correct
22 Correct 1006 ms 38484 KB Output is correct
23 Correct 161 ms 16876 KB Output is correct
24 Correct 105 ms 9952 KB Output is correct
25 Correct 115 ms 11876 KB Output is correct
26 Correct 114 ms 11872 KB Output is correct
27 Correct 163 ms 15604 KB Output is correct
28 Correct 159 ms 16748 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 2 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 389 ms 19564 KB Output is correct
34 Correct 755 ms 34736 KB Output is correct
35 Correct 1049 ms 46216 KB Output is correct
36 Correct 1404 ms 57312 KB Output is correct
37 Correct 340 ms 24648 KB Output is correct
38 Correct 324 ms 29128 KB Output is correct
39 Correct 333 ms 24648 KB Output is correct
40 Correct 327 ms 29128 KB Output is correct
41 Correct 336 ms 24776 KB Output is correct
42 Correct 317 ms 29124 KB Output is correct
43 Correct 159 ms 15604 KB Output is correct
44 Correct 158 ms 16876 KB Output is correct
45 Correct 127 ms 13132 KB Output is correct
46 Correct 178 ms 13132 KB Output is correct
47 Correct 478 ms 22348 KB Output is correct
48 Correct 1038 ms 42208 KB Output is correct
49 Correct 123 ms 12896 KB Output is correct
50 Correct 124 ms 12768 KB Output is correct
51 Correct 130 ms 12768 KB Output is correct
52 Correct 121 ms 12768 KB Output is correct
53 Correct 119 ms 12772 KB Output is correct
54 Correct 120 ms 12768 KB Output is correct