oj.uz

Submission #684810

# Submission time Handle Problem Language Result Execution time Memory
684810 2023-01-22T13:46:48 Z KiriLL1ca Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1450 ms 324200 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
#define pb push_back
#define fr first
#define sc second
#define pw(x) (1ll << x)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

struct do_2d {
    struct fen {
        vector <int> t, cp;
        inline void make () { sort(all(cp)); cp.erase(unique(all(cp)), cp.end()); t.resize(sz(cp) + 100); }
        inline void _upd (int p, int x) { for (p += 5; p < sz(t); p += (p & -p)) t[p] += x; }
        inline int _get (int p) { int res = 0; for (p += 5; p; p -= (p & -p)) res += t[p]; return res; }
        inline void upd (int p, int x) {
            p = lower_bound(all(cp), p) - cp.begin();
            _upd(0, x); _upd(p + 1, -x);
        }
        inline int get (int r) {
            r = lower_bound(all(cp), r) - cp.begin();
            return _get(r);
        }
        inline int get (int l, int r) { return get(r) - get(l - 1); }
    };

    int n;
    vector <fen> t;
    do_2d (int n = 0) : n(n), t(4 * n) {}

    inline void add (int v, int tl, int tr, int l, int r, int x) {
        if (tl > r || l > tr) return;
        if (l <= tl && tr <= r) return void(t[v].cp.pb(x));
        int tm = (tl + tr) >> 1;
        add(v << 1, tl, tm, l, r, x); add(v << 1 | 1, tm + 1, tr, l, r, x);
    }
    inline void build (int v, int tl, int tr) {
        t[v].make();
        if (tl == tr) return;
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm); build(v << 1 | 1, tm + 1, tr);
    }

    inline void upd (int v, int tl, int tr, int l, int r, int x, int y) {
        if (l > tr || tl > r) return;
        if (l <= tl && tr <= r) return void(t[v].upd(x, y));
        int tm = (tl + tr) >> 1;
        upd(v << 1, tl, tm, l, r, x, y);
        upd(v << 1 | 1, tm + 1, tr, l, r, x, y);
    }

    inline int get (int v, int tl, int tr, int x, int y) {
        int res = t[v].get(y);
        if (tl == tr) return res;
        int tm = (tl + tr) >> 1;
        if (x <= tm) return res + get(v << 1, tl, tm, x, y);
        else return res + get(v << 1 | 1, tm + 1, tr, x, y);
    }

    inline void add (int l, int r, int x) { add(1, 0, n - 1, l, r, x); }
    inline void build () { build(1, 0, n - 1); }
    inline void upd (int l, int r, int x, int y) { upd(1, 0, n - 1, l, r, x, y); }
    inline int get (int x, int y) { return get(1, 0, n - 1, x, y); }
};

inline void solve () {
    int n, q; cin >> n >> q;
    string s; cin >> s;
    vector <array <int, 3>> req (q);
    for (int i = 0; i < q; ++i) {
        string t; cin >> t;
        if (t == "toggle") {
            int id; cin >> id; --id;
            req[i] = {0, id, -1};
        }
        else {
            int l, r; cin >> l >> r; --l, --r;
            req[i] = {1, l, r};
        }
    }

    set <array <int, 3>> seg;
    vector <int> lamp (n);
    for (int i = 0; i < n; ++i) lamp[i] = s[i] - '0';

    for (int i = 0, j; i < n; ) {
        j = i;
        while (j < n && lamp[i] == lamp[j]) ++j;
        if (lamp[i]) seg.insert({i, j, 0});
        i = j;
    }

    const int inf = 1e9 + 7;

    function <set <array <int, 3>>::iterator(int x)> get_iter = [&] (int x) {
        auto it = seg.upper_bound({x, inf, inf});
        if (it != seg.begin()) --it;
        if (it == seg.end()) return seg.end();
        auto [l, r, _] = *it;
        if (l <= x && x <= r) return it;
        else return seg.end();
    };

    do_2d st (n + 1);
    for (auto [l, r, time] : seg) st.add(l, r, r);

    int time = 1;
    for (auto [tp, i, _] : req) {
        if (tp) continue;
        if (lamp[i]) {
            lamp[i] = 0;
            auto it = get_iter(i);
            auto [l, r, t] = *it; seg.erase(it);
            if (l < i) {
                seg.insert({l, i, time});
                st.add(l, i, i);
            }
            if (i + 1 < r) {
                seg.insert({i + 1, r, time});
                st.add(i + 1, r, r);
            }
        }
        else {
            lamp[i] = 1;
            int l = i, r = i + 1;
            auto it = get_iter(r);
            if (it != seg.end()) {
                r = (*it)[1];
                seg.erase(it);
            }
            it = get_iter(l);
            if (it != seg.end()) {
                l = (*it)[0];
                seg.erase(it);
            }

            seg.insert({l, r, time});
            st.add(l, r, r);
        }
        ++time;
    }
    st.build();

    seg.clear();
    for (int i = 0; i < n; ++i) lamp[i] = s[i] - '0';

    for (int i = 0, j; i < n; ) {
        j = i;
        while (j < n && lamp[i] == lamp[j]) ++j;
        if (lamp[i]) seg.insert({i, j, 0});
        i = j;
    }

    time = 1;
    for (auto [tp, l, r] : req) {
        if (tp) {
            int res = st.get(l, r);
            auto it = get_iter(l);
            if (it != seg.end() && (*it)[1] >= r) {
                res += time - (*it)[2];
            }
            cout << res << endl;
        }
        else {
            int i = l;
            if (lamp[i]) {
                lamp[i] = 0;
                auto it = get_iter(i);
                auto [l, r, t] = *it; seg.erase(it);
                st.upd(l, r, r, time - t);
                if (l < i) {
                    seg.insert({l, i, time});
                }
                if (i + 1 < r) {
                    seg.insert({i + 1, r, time});
                }
            }
            else {
                lamp[i] = 1;
                int l = i, r = i + 1;
                auto it = get_iter(r);
                if (it != seg.end()) {
                    r = (*it)[1];
                    st.upd(i + 1, r, r, time - (*it)[2]);
                    seg.erase(it);
                }
                it = get_iter(l);
                if (it != seg.end()) {
                    l = (*it)[0];
                    st.upd(l, i, i, time - (*it)[2]);
                    seg.erase(it);
                }
                seg.insert({l, r, time});
            }
        }
        ++time;
    }
}

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

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL
    int t = 1; // cin >> t;
    while (t--) solve();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 316 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 7508 KB Output is correct
2 Correct 378 ms 7628 KB Output is correct
3 Correct 479 ms 13116 KB Output is correct
4 Correct 1204 ms 320400 KB Output is correct
5 Correct 1308 ms 321888 KB Output is correct
6 Correct 1169 ms 321148 KB Output is correct
7 Correct 767 ms 307580 KB Output is correct
8 Correct 877 ms 308812 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 3 ms 1352 KB Output is correct
3 Correct 3 ms 1360 KB Output is correct
4 Correct 2 ms 1364 KB Output is correct
5 Correct 1310 ms 324200 KB Output is correct
6 Correct 1378 ms 324100 KB Output is correct
7 Correct 1450 ms 321688 KB Output is correct
8 Correct 866 ms 309492 KB Output is correct
9 Correct 368 ms 5152 KB Output is correct
10 Correct 388 ms 5324 KB Output is correct
11 Correct 377 ms 5652 KB Output is correct
12 Correct 795 ms 308064 KB Output is correct
13 Correct 809 ms 309512 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 2 ms 1352 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Correct 2 ms 1364 KB Output is correct
5 Correct 996 ms 316776 KB Output is correct
6 Correct 1081 ms 318896 KB Output is correct
7 Correct 1173 ms 320852 KB Output is correct
8 Correct 1193 ms 322908 KB Output is correct
9 Correct 328 ms 8420 KB Output is correct
10 Correct 244 ms 8408 KB Output is correct
11 Correct 331 ms 8640 KB Output is correct
12 Correct 231 ms 8188 KB Output is correct
13 Correct 340 ms 8404 KB Output is correct
14 Correct 235 ms 8464 KB Output is correct
15 Correct 776 ms 307592 KB Output is correct
16 Correct 787 ms 309052 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 364 ms 7508 KB Output is correct
9 Correct 378 ms 7628 KB Output is correct
10 Correct 479 ms 13116 KB Output is correct
11 Correct 1204 ms 320400 KB Output is correct
12 Correct 1308 ms 321888 KB Output is correct
13 Correct 1169 ms 321148 KB Output is correct
14 Correct 767 ms 307580 KB Output is correct
15 Correct 877 ms 308812 KB Output is correct
16 Correct 2 ms 1364 KB Output is correct
17 Correct 3 ms 1352 KB Output is correct
18 Correct 3 ms 1360 KB Output is correct
19 Correct 2 ms 1364 KB Output is correct
20 Correct 1310 ms 324200 KB Output is correct
21 Correct 1378 ms 324100 KB Output is correct
22 Correct 1450 ms 321688 KB Output is correct
23 Correct 866 ms 309492 KB Output is correct
24 Correct 368 ms 5152 KB Output is correct
25 Correct 388 ms 5324 KB Output is correct
26 Correct 377 ms 5652 KB Output is correct
27 Correct 795 ms 308064 KB Output is correct
28 Correct 809 ms 309512 KB Output is correct
29 Correct 3 ms 1364 KB Output is correct
30 Correct 2 ms 1352 KB Output is correct
31 Correct 2 ms 1364 KB Output is correct
32 Correct 2 ms 1364 KB Output is correct
33 Correct 996 ms 316776 KB Output is correct
34 Correct 1081 ms 318896 KB Output is correct
35 Correct 1173 ms 320852 KB Output is correct
36 Correct 1193 ms 322908 KB Output is correct
37 Correct 328 ms 8420 KB Output is correct
38 Correct 244 ms 8408 KB Output is correct
39 Correct 331 ms 8640 KB Output is correct
40 Correct 231 ms 8188 KB Output is correct
41 Correct 340 ms 8404 KB Output is correct
42 Correct 235 ms 8464 KB Output is correct
43 Correct 776 ms 307592 KB Output is correct
44 Correct 787 ms 309052 KB Output is correct
45 Correct 200 ms 5196 KB Output is correct
46 Correct 253 ms 5156 KB Output is correct
47 Correct 578 ms 110116 KB Output is correct
48 Correct 1131 ms 320260 KB Output is correct
49 Correct 429 ms 5456 KB Output is correct
50 Correct 413 ms 5472 KB Output is correct
51 Correct 448 ms 5668 KB Output is correct
52 Correct 423 ms 5900 KB Output is correct
53 Correct 435 ms 5860 KB Output is correct
54 Correct 434 ms 5976 KB Output is correct