oj.uz

Submission #848685

# Submission time Handle Problem Language Result Execution time Memory
848685 2023-09-13T09:32:18 Z hngwlog Street Lamps (APIO19_street_lamps) C++14
40 / 100
 84 ms 20220 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

struct queryNode {

    string type;
    int id, a, b;
};

int n, q;
string s;
vector<int> a;
vector<queryNode> qu;

namespace subtask1 {

    void main() {

        vector<vector<int>> c(q + 1, vector<int>(n + 1));
        FOR(i, 1, n) c[0][i] = a[i] + c[0][i - 1];
        REP(i, q) {
            FOR(j, 1, n) c[i + 1][j] = c[i][j] - c[i][j - 1];
            if (i && qu[i - 1].type == "toggle") c[i + 1][qu[i - 1].id] = 1 - c[i + 1][qu[i - 1].id];
            FOR(j, 1, n) c[i + 1][j] += c[i + 1][j - 1];
            if (qu[i].type == "query") {
                int a = qu[i].a, b = qu[i].b - 1;
                int ans = 0;
                FOR(j, 1, i + 1) ans += (c[j][b] - c[j][a - 1] == b - a + 1);
                cout << ans << '\n';
            }
        }
    }
}

bool checkSub2() {

    REP(i, q) {
        if (qu[i].type == "toggle") continue;
        if (qu[i].b - qu[i].a != 1) return false;
    }
    return true;
}

namespace subtask2 {

    void main() {

        vector<int> ans(n + 1), in(n + 1, - 1);
        FOR(i, 1, n) if (a[i] == 1) in[i] = 1;
        REP(i, q) {
            if (i && qu[i - 1].type == "toggle") {
                int id  = qu[i - 1].id;
                if (!a[id]) {
                    a[id] = 1 - a[id];
                    in[id] = i + 1;
                }
                else {
                    a[id] = 0;
                    ans[id] += (i + 1) - in[id];
                    in[id] = - 1;
                }
            }
            if (qu[i].type == "query") cout << ans[qu[i].a] + (in[qu[i].a] != - 1 ? i + 1 - in[qu[i].a] + 1 : 0) << '\n';
        }
    }
}

bool checkSub3() {

    vector<int> b(n + 1);
    FOR(i, 1, n) b[i] = a[i];
    REP(i, q) {
        if (qu[i].type == "toggle") {
            int id = qu[i].id;
            if (b[id] != 1) return false;
            b[id] = 1 - b[id];
        }
    }
    return true;
}

namespace subtask3 {

    const int inf = 1e9;

    struct segTree {

        vector<int> ST;

        void init(int n) {

            ST.assign(4 * n + 4, inf);
        }

        void update(int id, int l, int r, int pos, int val) {

            if (pos < l || r < pos) return ;
            if (l == r) {
                ST[id] = min(ST[id], val);
                return ;
            }
            int mid = (l + r) / 2;
            update(id * 2, l, mid, pos, val);
            update(id * 2 + 1, mid + 1, r, pos, val);
            ST[id] = min(ST[id * 2], ST[id * 2 + 1]);
        }

        int get(int id, int l, int r, int u, int v) {

            if (r < u || v < l) return inf;
            if (u <= l && r <= v) return ST[id];
            int mid = (l + r) / 2;
            return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
        }
    } st;

    void main() {

        st.init(n);
        FOR(i, 1, n) if (!a[i]) st.update(1, 1, n, i, 0);
        REP(i, q) {
            if (i && qu[i - 1].type == "toggle") {
                int id = qu[i - 1].id;
                st.update(1, 1, n, id, i);
            }
            if (qu[i].type == "query") {
                int a = qu[i].a, b = qu[i].b - 1;
                cout << min(i + 1, st.get(1, 1, n, a, b)) << '\n';
            }
        }
    }
}

bool checkSub4() {

    int cnt = 0;
    REP(i, q) {
        if (qu[i].type == "toggle" && cnt) return false;
        cnt += (qu[i].type == "query");
    }
    return true;
}

namespace subtask4 {

    void main() {


    }
}

int main() {
    fastio;

    cin >> n >> q;
    cin >> s;
    a.resize(n + 1);
    FOR(i, 1, n) a[i] = s[i - 1] - '0';
    qu.resize(q);
    REP(i, q) {
        cin >> qu[i].type;
        if (qu[i].type == "toggle") cin >> qu[i].id;
        else cin >> qu[i].a >> qu[i].b;
    }
    if (n <= 100 && q <= 100) subtask1::main();
    else if (checkSub2()) subtask2::main();
    else if (checkSub3()) subtask3::main();
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15440 KB Output is correct
2 Correct 65 ms 15444 KB Output is correct
3 Correct 70 ms 15440 KB Output is correct
4 Correct 78 ms 19092 KB Output is correct
5 Correct 81 ms 19452 KB Output is correct
6 Correct 71 ms 18916 KB Output is correct
7 Correct 82 ms 18916 KB Output is correct
8 Correct 84 ms 20220 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 63 ms 15440 KB Output is correct
9 Correct 65 ms 15444 KB Output is correct
10 Correct 70 ms 15440 KB Output is correct
11 Correct 78 ms 19092 KB Output is correct
12 Correct 81 ms 19452 KB Output is correct
13 Correct 71 ms 18916 KB Output is correct
14 Correct 82 ms 18916 KB Output is correct
15 Correct 84 ms 20220 KB Output is correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -