oj.uz

Submission #935256

# Submission time Handle Problem Language Result Execution time Memory
935256 2024-02-29T01:36:43 Z peterandvoi Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2197 ms 217040 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = (int) 3e5 + 5;

int n, q;
int t[N], l[N], r[N], p[N];
string s;
vector<int> f[N], tree[N];
vector<tuple<int, int, int>> seg[N];

void fake_get(int u, int v) {
    for (int x = u; x > 0; x -= x & -x) {
        for (int y = v; y <= n; y += y & -y) {
            tree[x].emplace_back(y);
        }
    }
}

void upd(int u, int v, int delta) {
    for (int x = u; x <= n; x += x & -x) {
        for (int y = upper_bound(tree[x].begin(), tree[x].end(), v) - tree[x].begin(); y > 0; y -= y & -y) {
            f[x][y] += delta;
        }
    }
}

int get(int u, int v) {
    int res = 0;
    for (int x = u; x > 0; x -= x & -x) {
        for (int y = lower_bound(tree[x].begin(), tree[x].end(), v) - tree[x].begin() + 1; y <= (int) tree[x].size(); y += y & -y) {
            res += f[x][y];
        }
    }
    return res;
}

namespace ft {
    int tree[N];

    void upd(int i, int x) {
        for (; i <= n; i += i & -i) {
            tree[i] += x;
        }
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }

    void reset() {
        memset(tree, 0, sizeof(tree));
    }
}

map<pair<int, int>, int> m;

void del(int l, int r, int cur, bool prep) {
    if (l <= r) {
        if (prep) {
            seg[cur].emplace_back(l, r, cur - m[{l, r}]);
        }
        m.erase({l, r});
    }
}

void add(int l, int r, int cur) {
    if (l <= r) {
        m[{l, r}] = cur;
    }
}

bool check(int l, int r) {
    return ft::get(l, r) == r - l + 1;
}

int findL(int i) {
    int l = 1, r = i - 1, res = i;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid, i - 1)) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

int findR(int i) {
    int l = i + 1, r = n, res = i;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(i + 1, mid)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

void flip(int i, int cur, bool prep) {
    int L = findL(i);
    int R = findR(i);
    if (s[i] == '1') {
        del(L, R, cur, prep);
        add(L, i - 1, cur);
        add(i + 1, R, cur);
        ft::upd(i, -1);
        s[i] = '0';
    } else {
        add(L, R, cur);
        del(L, i - 1, cur, prep);
        del(i + 1, R, cur, prep);
        ft::upd(i, 1);
        s[i] = '1';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> q >> s;
    s = '&' + s;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '1') {
            ft::upd(i, 1);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '1') {
            int j = i;
            while (j <= n && s[j] == '1') {
                j++;
            }
            m[{i, j - 1}] = 0;
            i = j - 1;
        }
    }
    for (int i = 1; i <= q; ++i) {
        string type;
        cin >> type;
        t[i] = type[0] == 'q' ? 0 : 1;
        if (t[i] == 0) {
            cin >> l[i] >> r[i];
            fake_get(l[i], r[i] - 1);
        } else {
            int j;
            cin >> j;
            p[i] = j;
            flip(j, i, true);
        }
    }
    for (int i = 1; i <= n; ++i) {
        sort(tree[i].begin(), tree[i].end());
        tree[i].erase(unique(tree[i].begin(), tree[i].end()), tree[i].end());
        f[i].resize((int) tree[i].size() + 1);
    }
    ft::reset();
    for (int i = q; i >= 1; --i) {
        if (t[i]) {
            int j = p[i];
            s[j] = s[j] == '0' ? '1' : '0';
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '1') {
            ft::upd(i, 1);
        }
    }
    m.clear();
    for (int i = 1; i <= q; ++i) {
        for (auto [l, r, v] : seg[i]) {
            upd(l, r, v);
        }
        if (t[i] == 0) {
            int res = get(l[i], r[i] - 1);
            if (check(l[i], r[i] - 1)) {
                int L = findL(l[i]);
                int R = findR(r[i] - 1);
                res += i - m[{L, R}];
            }
            cout << res << "\n";
        } else {
            int j = p[i];
            flip(j, i, false);
        }
    }
}

Compilation message

street_lamps.cpp: In function 'int findL(int)':
street_lamps.cpp:95:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |         int mid = l + r >> 1;
      |                   ~~^~~
street_lamps.cpp: In function 'int findR(int)':
street_lamps.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 27132 KB Output is correct
2 Correct 6 ms 27140 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 6 ms 27228 KB Output is correct
5 Correct 6 ms 27136 KB Output is correct
6 Correct 6 ms 27228 KB Output is correct
7 Correct 6 ms 27240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 43188 KB Output is correct
2 Correct 309 ms 48524 KB Output is correct
3 Correct 610 ms 64304 KB Output is correct
4 Correct 1623 ms 129036 KB Output is correct
5 Correct 1823 ms 138792 KB Output is correct
6 Correct 1545 ms 113448 KB Output is correct
7 Correct 1622 ms 190544 KB Output is correct
8 Correct 1810 ms 192388 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27224 KB Output is correct
2 Correct 7 ms 27228 KB Output is correct
3 Correct 7 ms 27332 KB Output is correct
4 Correct 8 ms 27404 KB Output is correct
5 Correct 1026 ms 54316 KB Output is correct
6 Correct 1404 ms 105040 KB Output is correct
7 Correct 1745 ms 152748 KB Output is correct
8 Correct 2133 ms 214004 KB Output is correct
9 Correct 159 ms 42020 KB Output is correct
10 Correct 166 ms 42164 KB Output is correct
11 Correct 195 ms 46496 KB Output is correct
12 Correct 1932 ms 212204 KB Output is correct
13 Correct 2181 ms 213668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27480 KB Output is correct
2 Correct 7 ms 27480 KB Output is correct
3 Correct 7 ms 27460 KB Output is correct
4 Correct 7 ms 27228 KB Output is correct
5 Correct 1955 ms 217040 KB Output is correct
6 Correct 1700 ms 169848 KB Output is correct
7 Correct 1358 ms 122036 KB Output is correct
8 Correct 1006 ms 56512 KB Output is correct
9 Correct 334 ms 43520 KB Output is correct
10 Correct 275 ms 38708 KB Output is correct
11 Correct 337 ms 43584 KB Output is correct
12 Correct 247 ms 38556 KB Output is correct
13 Correct 334 ms 43460 KB Output is correct
14 Correct 245 ms 38860 KB Output is correct
15 Correct 1891 ms 212104 KB Output is correct
16 Correct 2197 ms 213612 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 27132 KB Output is correct
2 Correct 6 ms 27140 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 6 ms 27228 KB Output is correct
5 Correct 6 ms 27136 KB Output is correct
6 Correct 6 ms 27228 KB Output is correct
7 Correct 6 ms 27240 KB Output is correct
8 Correct 225 ms 43188 KB Output is correct
9 Correct 309 ms 48524 KB Output is correct
10 Correct 610 ms 64304 KB Output is correct
11 Correct 1623 ms 129036 KB Output is correct
12 Correct 1823 ms 138792 KB Output is correct
13 Correct 1545 ms 113448 KB Output is correct
14 Correct 1622 ms 190544 KB Output is correct
15 Correct 1810 ms 192388 KB Output is correct
16 Correct 7 ms 27224 KB Output is correct
17 Correct 7 ms 27228 KB Output is correct
18 Correct 7 ms 27332 KB Output is correct
19 Correct 8 ms 27404 KB Output is correct
20 Correct 1026 ms 54316 KB Output is correct
21 Correct 1404 ms 105040 KB Output is correct
22 Correct 1745 ms 152748 KB Output is correct
23 Correct 2133 ms 214004 KB Output is correct
24 Correct 159 ms 42020 KB Output is correct
25 Correct 166 ms 42164 KB Output is correct
26 Correct 195 ms 46496 KB Output is correct
27 Correct 1932 ms 212204 KB Output is correct
28 Correct 2181 ms 213668 KB Output is correct
29 Correct 7 ms 27480 KB Output is correct
30 Correct 7 ms 27480 KB Output is correct
31 Correct 7 ms 27460 KB Output is correct
32 Correct 7 ms 27228 KB Output is correct
33 Correct 1955 ms 217040 KB Output is correct
34 Correct 1700 ms 169848 KB Output is correct
35 Correct 1358 ms 122036 KB Output is correct
36 Correct 1006 ms 56512 KB Output is correct
37 Correct 334 ms 43520 KB Output is correct
38 Correct 275 ms 38708 KB Output is correct
39 Correct 337 ms 43584 KB Output is correct
40 Correct 247 ms 38556 KB Output is correct
41 Correct 334 ms 43460 KB Output is correct
42 Correct 245 ms 38860 KB Output is correct
43 Correct 1891 ms 212104 KB Output is correct
44 Correct 2197 ms 213612 KB Output is correct
45 Correct 87 ms 33308 KB Output is correct
46 Correct 159 ms 36676 KB Output is correct
47 Correct 829 ms 85012 KB Output is correct
48 Correct 1633 ms 139168 KB Output is correct
49 Correct 176 ms 45352 KB Output is correct
50 Correct 165 ms 43436 KB Output is correct
51 Correct 212 ms 48520 KB Output is correct
52 Correct 273 ms 55104 KB Output is correct
53 Correct 276 ms 55212 KB Output is correct
54 Correct 274 ms 55104 KB Output is correct