oj.uz

Submission #977828

# Submission time Handle Problem Language Result Execution time Memory
977828 2024-05-08T11:37:19 Z ZHIRDILBILDIZ Street Lamps (APIO19_street_lamps) C++14
60 / 100
 719 ms 170936 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;
const int N = 3e5 + 10;

int p[N];
int ans[N];
set<int> qr[N];
vector<int> gr[N];
void init(int _sz) {
    for (int i = 1; i <= _sz; ++i)
        p[i] = i,
            gr[i].push_back(i);
}
void join (int u, int v, int w) {
    u = p[u];
    v = p[v];
    if (u == v)
        return;
    if (gr[u].size() + qr[u].size() > gr[v].size() + qr[v].size())
        swap(u, v);
    for (int i : gr[u]) {
        p[i] = v;
        gr[v].push_back(i);
    }
    for (int i : qr[u])
        if (qr[v].find(i) != qr[v].end())
            ans[i] = max(ans[i], i - w);
        else
            qr[v].insert(i);
}
signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    while (t--) {
        int n, q;
        cin >> n >> q;
        char a[n + 1];
        char for_sub3[n + 1];
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            for_sub3[i] = a[i];
        }
        bool sub2 = 1;
        bool sub3 = 1;
        string type[q + 1];
        int c[q + 1], d[q + 1];
        bool abu[q + 1] = {};

        for (int i = 1; i <= q; ++i) {
            cin >> type[i] >> c[i];
            if (type[i] == "query") {
                cin >> d[i];
                abu[i] = 1;
                if (d[i] - c[i] != 1)
                    sub2 = 0;
            } else {
                if (for_sub3[c[i]] == '1')
                    sub3 = 0;
                else
                    for_sub3[c[i]] = '1';
            }
        }

        if (sub3) {
            init(n + 1);

            for (int i = 1; i <= q; ++i)
                if (type[i] == "query")
                    qr[c[i]].insert(i),
                        qr[d[i]].insert(i);

            for (int i = 1; i <= n; ++i)
                if (a[i] == '1')
                    join(i, i + 1, 0);

            for (int i = 1; i <= q; ++i)
                if (type[i] == "toggle")
                    join(c[i], c[i] + 1, i);

            for (int i = 1; i <= q; ++i)
                if (abu[i])
                    cout << ans[i] << '\n';
            continue;
        }

        if (sub2) {
            vector<pair<bool, int>> query[n + 1];

            for (int i = 1; i <= q; ++i)
                if (type[i] == "toggle")
                    query[c[i]].push_back({0, i});
                else
                    query[c[i]].push_back({1, i});

            for (int i = 1; i <= n; ++i) {
                pair<char, int> now = {a[i], 0};
                int cnt = 0;
                now = {a[i], 0};
                for (auto j : query[i]) {
                    if (j.fi) {
                        ans[j.se] = cnt + (now.fi == '1') * (j.se - now.se);
                    } else {
                        if (now.fi == '1') {
                            cnt += (j.se - now.se);
                            now.fi = '0';
                        } else {
                            now.fi = '1';
                        }
                        now.se = j.se;
                    }
                }
            }
            for (int i = 1; i <= q; ++i)
                if (abu[i])
                    cout << ans[i] << '\n';
            continue;
        }

        if (n <= 100 && q <= 100) {
            bool b[n + 1][q + 1] = {};
            for (int j = 1; j <= n; ++j)
                b[j][0] = a[j] - '0';
            for (int i = 1; i <= q; ++i) {
                if (type[i] == "toggle") {
                    if (a[c[i]] == '1')
                        a[c[i]] = '0';
                    else
                        a[c[i]] = '1';
                }
                for (int j = 1; j <= n; ++j)
                    b[j][i] = a[j] - '0';
                if (type[i] == "query") {
                    int ans = 0;
                    for (int j = 0; j < i; ++j) {
                        bool flag = 1;
                        for (int z = c[i]; z < d[i]; ++z)
                            flag &= (b[z][j]);
                        ans += flag;
                    }
                    cout << ans << '\n';
                }
            }
            continue;
        }

    }

    return 0;
}

// 10 9
// 1101110100
// query 1 2
// toggle 3 
// query 1 6
// query 1 6
// toggle 10
// query 10 11
// query 9 10
// toggle 9
// query 9 10

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23136 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 6 ms 22976 KB Output is correct
4 Correct 5 ms 23132 KB Output is correct
5 Correct 7 ms 22992 KB Output is correct
6 Correct 7 ms 23128 KB Output is correct
7 Correct 6 ms 22984 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 39248 KB Output is correct
2 Correct 89 ms 39352 KB Output is correct
3 Correct 97 ms 40072 KB Output is correct
4 Correct 121 ms 49884 KB Output is correct
5 Correct 511 ms 124288 KB Output is correct
6 Correct 127 ms 52624 KB Output is correct
7 Correct 258 ms 78100 KB Output is correct
8 Correct 452 ms 94732 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23148 KB Output is correct
2 Correct 8 ms 23384 KB Output is correct
3 Correct 6 ms 23516 KB Output is correct
4 Correct 6 ms 23388 KB Output is correct
5 Correct 189 ms 61884 KB Output is correct
6 Correct 496 ms 114924 KB Output is correct
7 Correct 719 ms 170936 KB Output is correct
8 Correct 651 ms 96148 KB Output is correct
9 Correct 281 ms 81628 KB Output is correct
10 Correct 332 ms 81752 KB Output is correct
11 Correct 333 ms 91732 KB Output is correct
12 Correct 331 ms 79556 KB Output is correct
13 Correct 619 ms 96188 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23136 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 6 ms 22976 KB Output is correct
4 Correct 5 ms 23132 KB Output is correct
5 Correct 7 ms 22992 KB Output is correct
6 Correct 7 ms 23128 KB Output is correct
7 Correct 6 ms 22984 KB Output is correct
8 Correct 78 ms 39248 KB Output is correct
9 Correct 89 ms 39352 KB Output is correct
10 Correct 97 ms 40072 KB Output is correct
11 Correct 121 ms 49884 KB Output is correct
12 Correct 511 ms 124288 KB Output is correct
13 Correct 127 ms 52624 KB Output is correct
14 Correct 258 ms 78100 KB Output is correct
15 Correct 452 ms 94732 KB Output is correct
16 Correct 5 ms 23148 KB Output is correct
17 Correct 8 ms 23384 KB Output is correct
18 Correct 6 ms 23516 KB Output is correct
19 Correct 6 ms 23388 KB Output is correct
20 Correct 189 ms 61884 KB Output is correct
21 Correct 496 ms 114924 KB Output is correct
22 Correct 719 ms 170936 KB Output is correct
23 Correct 651 ms 96148 KB Output is correct
24 Correct 281 ms 81628 KB Output is correct
25 Correct 332 ms 81752 KB Output is correct
26 Correct 333 ms 91732 KB Output is correct
27 Correct 331 ms 79556 KB Output is correct
28 Correct 619 ms 96188 KB Output is correct
29 Incorrect 5 ms 23128 KB Output isn't correct
30 Halted 0 ms 0 KB -