oj.uz

Submission #558219

# Submission time Handle Problem Language Result Execution time Memory
558219 2022-05-07T04:33:20 Z hoanghq2004 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2674 ms 109664 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

int n, q;
struct Query {
    int x, y, u, v, d, type;
};

vector <Query> work;
vector <int> fake[N], BIT[N];

void add_fake(int x, int y) {
    for (; x < N; x += x & - x)
        fake[x].push_back(y);
}

void add(int x, int y, int d) {
    for (; x < N; x += x & - x) {
        int t = lower_bound(fake[x].begin(), fake[x].end(), y) - fake[x].begin() + 1;
        for (; t < BIT[x].size(); t += t & - t) BIT[x][t] += d;
    }
}

int get(int x, int y) {
    int ans = 0;
    for (; x; x -= x & - x) {
        int t = upper_bound(fake[x].begin(), fake[x].end(), y) - fake[x].begin();
        for (; t; t -= t & - t)
            ans += BIT[x][t];
    }
    return ans;
}

void add(int x, int y, int u, int v, int d) {
    add(x, u, d);
    add(y + 1, u, - d);
    add(x, v + 1, - d);
    add(y + 1, v + 1, d);
}

void push(int x, int y, int u, int v, int d) {
    work.push_back({x, y, u, v, d, 0});
    add_fake(x, u);
    add_fake(y + 1, u);
    add_fake(x, v + 1);
    add_fake(y + 1, v + 1);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    set <int> s;
    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;
        if (c == '0') s.insert(i);
    }
    for (int T = 1; T <= q; ++T) {
        string cmd;
        cin >> cmd;
        if (cmd == "toggle") {
            int i;
            cin >> i;
            int L = 1, R = n;
            if (s.find(i) == s.end()) {
                auto iter = s.lower_bound(i);
                if (iter != s.end()) R = *iter - 1;
                if (iter != s.begin()) L = *(--iter) + 1;
                push(L, i, i, R, T);
                s.insert(i);
            } else {
                s.erase(i);
                auto iter = s.lower_bound(i);
                if (iter != s.end()) R = *iter - 1;
                if (iter != s.begin()) L = *(--iter) + 1;
                push(L, i, i, R, - T);
            }
        } else {
            int L, R;
            cin >> L >> R;
            --R;
            int cur = 0;
            auto iter = s.lower_bound(L);
            if (iter == s.end() || *iter > R) cur += T;
            work.push_back({L, R, L, R, cur, 1});
        }
    }
    for (int i = 0; i < N; ++i) {
        sort(fake[i].begin(), fake[i].end());
        fake[i].erase(unique(fake[i].begin(), fake[i].end()), fake[i].end());
        BIT[i].assign(fake[i].size() + 5, 0);
    }
    for (auto [x, y, u, v, d, type]: work) {
        if (type == 0) {
            add(x, y, u, v, d);
        } else {
            cout << d + get(x, y) << '\n';
        }
    }
}

Compilation message

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (; t < BIT[x].size(); t += t & - t) BIT[x][t] += d;
      |                ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:104:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |     for (auto [x, y, u, v, d, type]: work) {
      |               ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23764 KB Output is correct
2 Correct 23 ms 23736 KB Output is correct
3 Correct 23 ms 23828 KB Output is correct
4 Correct 22 ms 23724 KB Output is correct
5 Correct 23 ms 23764 KB Output is correct
6 Correct 22 ms 23764 KB Output is correct
7 Correct 22 ms 23756 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 79956 KB Output is correct
2 Correct 859 ms 75684 KB Output is correct
3 Correct 1074 ms 72704 KB Output is correct
4 Correct 1564 ms 85328 KB Output is correct
5 Correct 1321 ms 70200 KB Output is correct
6 Correct 1759 ms 93888 KB Output is correct
7 Correct 419 ms 51452 KB Output is correct
8 Correct 156 ms 38784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24140 KB Output is correct
2 Correct 29 ms 24132 KB Output is correct
3 Correct 35 ms 23940 KB Output is correct
4 Correct 24 ms 23764 KB Output is correct
5 Correct 2674 ms 108708 KB Output is correct
6 Correct 1989 ms 93168 KB Output is correct
7 Correct 1258 ms 69524 KB Output is correct
8 Correct 152 ms 38812 KB Output is correct
9 Correct 105 ms 33184 KB Output is correct
10 Correct 127 ms 34124 KB Output is correct
11 Correct 106 ms 34144 KB Output is correct
12 Correct 434 ms 51380 KB Output is correct
13 Correct 150 ms 38776 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 35 ms 23888 KB Output is correct
3 Correct 36 ms 24012 KB Output is correct
4 Correct 33 ms 24148 KB Output is correct
5 Correct 371 ms 40292 KB Output is correct
6 Correct 1049 ms 66476 KB Output is correct
7 Correct 1719 ms 88660 KB Output is correct
8 Correct 2533 ms 109664 KB Output is correct
9 Correct 1151 ms 88828 KB Output is correct
10 Correct 1357 ms 107196 KB Output is correct
11 Correct 1168 ms 89052 KB Output is correct
12 Correct 1356 ms 107416 KB Output is correct
13 Correct 1168 ms 88940 KB Output is correct
14 Correct 1325 ms 107332 KB Output is correct
15 Correct 408 ms 45724 KB Output is correct
16 Correct 172 ms 33008 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23764 KB Output is correct
2 Correct 23 ms 23736 KB Output is correct
3 Correct 23 ms 23828 KB Output is correct
4 Correct 22 ms 23724 KB Output is correct
5 Correct 23 ms 23764 KB Output is correct
6 Correct 22 ms 23764 KB Output is correct
7 Correct 22 ms 23756 KB Output is correct
8 Correct 737 ms 79956 KB Output is correct
9 Correct 859 ms 75684 KB Output is correct
10 Correct 1074 ms 72704 KB Output is correct
11 Correct 1564 ms 85328 KB Output is correct
12 Correct 1321 ms 70200 KB Output is correct
13 Correct 1759 ms 93888 KB Output is correct
14 Correct 419 ms 51452 KB Output is correct
15 Correct 156 ms 38784 KB Output is correct
16 Correct 30 ms 24140 KB Output is correct
17 Correct 29 ms 24132 KB Output is correct
18 Correct 35 ms 23940 KB Output is correct
19 Correct 24 ms 23764 KB Output is correct
20 Correct 2674 ms 108708 KB Output is correct
21 Correct 1989 ms 93168 KB Output is correct
22 Correct 1258 ms 69524 KB Output is correct
23 Correct 152 ms 38812 KB Output is correct
24 Correct 105 ms 33184 KB Output is correct
25 Correct 127 ms 34124 KB Output is correct
26 Correct 106 ms 34144 KB Output is correct
27 Correct 434 ms 51380 KB Output is correct
28 Correct 150 ms 38776 KB Output is correct
29 Correct 23 ms 23800 KB Output is correct
30 Correct 35 ms 23888 KB Output is correct
31 Correct 36 ms 24012 KB Output is correct
32 Correct 33 ms 24148 KB Output is correct
33 Correct 371 ms 40292 KB Output is correct
34 Correct 1049 ms 66476 KB Output is correct
35 Correct 1719 ms 88660 KB Output is correct
36 Correct 2533 ms 109664 KB Output is correct
37 Correct 1151 ms 88828 KB Output is correct
38 Correct 1357 ms 107196 KB Output is correct
39 Correct 1168 ms 89052 KB Output is correct
40 Correct 1356 ms 107416 KB Output is correct
41 Correct 1168 ms 88940 KB Output is correct
42 Correct 1325 ms 107332 KB Output is correct
43 Correct 408 ms 45724 KB Output is correct
44 Correct 172 ms 33008 KB Output is correct
45 Correct 394 ms 61276 KB Output is correct
46 Correct 508 ms 56196 KB Output is correct
47 Correct 951 ms 60612 KB Output is correct
48 Correct 1552 ms 85300 KB Output is correct
49 Correct 124 ms 34972 KB Output is correct
50 Correct 114 ms 34976 KB Output is correct
51 Correct 118 ms 35100 KB Output is correct
52 Correct 137 ms 35376 KB Output is correct
53 Correct 122 ms 35464 KB Output is correct
54 Correct 156 ms 35328 KB Output is correct