oj.uz

Submission #903805

# Submission time Handle Problem Language Result Execution time Memory
903805 2024-01-11T11:28:46 Z Trisanu_Das Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2327 ms 72000 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

struct Query {
    bool isToggle;
    int left, right, time, delta;
};

const int N = 1 << 19;
Query a[3 * N], b[3 * N];
int q, ans[N];

void cdq2(int l, int r) {
    if (r - l == 1) return;
    int m = (l + r) >> 1;
    cdq2(l, m);
    cdq2(m, r);

    for (int i = l; i < r; ++i)
        b[i].right = i < m;

    inplace_merge(b + l, b + m, b + r, [&](Query a, Query b) { return a.time < b.time; });

    int s = 0;
    for (int i = l; i < r; ++i) {
        if (!b[i].isToggle && b[i].left && b[i].right)
            s += b[i].delta * b[i].time;

        if (b[i].isToggle && !b[i].left && !b[i].right)
            ans[b[i].time] += s;
    }
}

void cdq1(int l, int r) {
    if (r - l == 1) return;
    int m = (l + r) >> 1;
    cdq1(l, m);
    cdq1(m, r);

    for (int i = l; i < r; ++i)
        a[i].left = i < m;

    merge(a + l, a + m, a + m, a + r, b + l, [&](Query a, Query b) {
        return pair(-a.right, a.isToggle) < pair(-b.right, b.isToggle);
    });

    for (int i = l; i < r; ++i)
        a[i] = b[i];

    cdq2(l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, p = 0;
    cin >> n >> q;

    int pre = -1;
    set<int> z = {-1};

    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;

        if (c != '0') {
            if (p && a[p - 1].right == i)
                a[p - 1].right = i + 1;
            else
                a[p++] = {0, pre + 1, i + 1, -1, -1};
        } else {
            z.insert(pre = i);
        }
    }

    z.insert(n);

    for (int t = 0; t < q; ++t) {
        string s;
        cin >> s;

        if (s == "toggle") {
            int i;
            cin >> i;
            --i;
            auto [it, f] = z.insert(i);
            int d = f ? +1 : -1;
            a[p++] = {0, *prev(it) + 1, *next(it), t, +d};
            a[p++] = {0, *prev(it) + 1, i, t, -d};
            a[p++] = {0, i + 1, *next(it), t, -d};
            if (d < 0)
                z.erase(it);
            ans[t] = -1;
        } else {
            int l, r;
            cin >> l >> r;
            --l;
            --r;
            a[p++] = {1, l, r, t, 0};
            ans[t] = *z.lower_bound(l) < r ? 0 : t;
        }
    }

    sort(a, a + p, [&](Query a, Query b) { return pair(a.left, a.isToggle) < pair(b.left, b.isToggle); });
    cdq1(0, p);

    for (int t = 0; t < q; ++t)
        if (0 <= ans[t])
            cout << ans[t] << '\n';

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4564 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1582 ms 40776 KB Output is correct
2 Correct 1648 ms 40788 KB Output is correct
3 Correct 1711 ms 40648 KB Output is correct
4 Correct 1908 ms 54048 KB Output is correct
5 Correct 1849 ms 47952 KB Output is correct
6 Correct 1800 ms 55880 KB Output is correct
7 Correct 931 ms 40180 KB Output is correct
8 Correct 712 ms 26440 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4440 KB Output is correct
2 Correct 4 ms 4440 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 2203 ms 72000 KB Output is correct
6 Correct 1985 ms 64300 KB Output is correct
7 Correct 1718 ms 48500 KB Output is correct
8 Correct 916 ms 25888 KB Output is correct
9 Correct 514 ms 23684 KB Output is correct
10 Correct 583 ms 23204 KB Output is correct
11 Correct 533 ms 23560 KB Output is correct
12 Correct 1120 ms 40808 KB Output is correct
13 Correct 957 ms 25924 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4576 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 4 ms 4440 KB Output is correct
4 Correct 4 ms 4728 KB Output is correct
5 Correct 1312 ms 37464 KB Output is correct
6 Correct 1626 ms 49360 KB Output is correct
7 Correct 1886 ms 55120 KB Output is correct
8 Correct 2327 ms 69532 KB Output is correct
9 Correct 1949 ms 47316 KB Output is correct
10 Correct 2179 ms 56504 KB Output is correct
11 Correct 1835 ms 47832 KB Output is correct
12 Correct 2289 ms 57528 KB Output is correct
13 Correct 1931 ms 46296 KB Output is correct
14 Correct 2290 ms 57396 KB Output is correct
15 Correct 1137 ms 39788 KB Output is correct
16 Correct 931 ms 25696 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4564 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1582 ms 40776 KB Output is correct
9 Correct 1648 ms 40788 KB Output is correct
10 Correct 1711 ms 40648 KB Output is correct
11 Correct 1908 ms 54048 KB Output is correct
12 Correct 1849 ms 47952 KB Output is correct
13 Correct 1800 ms 55880 KB Output is correct
14 Correct 931 ms 40180 KB Output is correct
15 Correct 712 ms 26440 KB Output is correct
16 Correct 5 ms 4440 KB Output is correct
17 Correct 4 ms 4440 KB Output is correct
18 Correct 4 ms 4444 KB Output is correct
19 Correct 2 ms 4440 KB Output is correct
20 Correct 2203 ms 72000 KB Output is correct
21 Correct 1985 ms 64300 KB Output is correct
22 Correct 1718 ms 48500 KB Output is correct
23 Correct 916 ms 25888 KB Output is correct
24 Correct 514 ms 23684 KB Output is correct
25 Correct 583 ms 23204 KB Output is correct
26 Correct 533 ms 23560 KB Output is correct
27 Correct 1120 ms 40808 KB Output is correct
28 Correct 957 ms 25924 KB Output is correct
29 Correct 3 ms 4576 KB Output is correct
30 Correct 3 ms 4444 KB Output is correct
31 Correct 4 ms 4440 KB Output is correct
32 Correct 4 ms 4728 KB Output is correct
33 Correct 1312 ms 37464 KB Output is correct
34 Correct 1626 ms 49360 KB Output is correct
35 Correct 1886 ms 55120 KB Output is correct
36 Correct 2327 ms 69532 KB Output is correct
37 Correct 1949 ms 47316 KB Output is correct
38 Correct 2179 ms 56504 KB Output is correct
39 Correct 1835 ms 47832 KB Output is correct
40 Correct 2289 ms 57528 KB Output is correct
41 Correct 1931 ms 46296 KB Output is correct
42 Correct 2290 ms 57396 KB Output is correct
43 Correct 1137 ms 39788 KB Output is correct
44 Correct 931 ms 25696 KB Output is correct
45 Correct 873 ms 29120 KB Output is correct
46 Correct 968 ms 28464 KB Output is correct
47 Correct 1123 ms 32492 KB Output is correct
48 Correct 1807 ms 54452 KB Output is correct
49 Correct 579 ms 23664 KB Output is correct
50 Correct 600 ms 24308 KB Output is correct
51 Correct 568 ms 25448 KB Output is correct
52 Correct 456 ms 25440 KB Output is correct
53 Correct 465 ms 24944 KB Output is correct
54 Correct 483 ms 25724 KB Output is correct