oj.uz

Submission #391310

# Submission time Handle Problem Language Result Execution time Memory
391310 2021-04-18T13:35:36 Z phathnv Street Lamps (APIO19_street_lamps) C++11
100 / 100
 2790 ms 100168 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 7;

struct Query{
    int type, a, b;
};

struct Bit2D{
    vector<int> nodes[N], d[N];
    void fakeUpdate(int x, int y){
        for(; x < N; x += x & -x)
            nodes[x].push_back(y);
    }
    void fakeQuery(int x, int y){
        for(; x > 0; x -= x & -x)
            nodes[x].push_back(y);
    }
    void normalize(){
        for(int i = 1; i < N; i++){
            sort(nodes[i].begin(), nodes[i].end());
            nodes[i].resize(unique(nodes[i].begin(), nodes[i].end()) - nodes[i].begin());
            d[i].assign(nodes[i].size() + 1, 0);
        }
    }
    void update(int x, int y, int val){
        for(; x < N; x += x & -x){
            int p = lower_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin() + 1;
            for(; p <= (int) nodes[x].size(); p += p & -p)
                d[x][p] += val;
        }
    }
    int query(int x, int y){
        int res = 0;
        for(; x > 0; x -= x & -x){
            int p = lower_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin() + 1;
            for(; p > 0; p -= p & -p)
                res += d[x][p];
        }
        return res;
    }
} bit;

int n, q, last[N];
Query queries[N];
string s, cur;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q >> s;
    s = '*' + s;
    for(int i = 1; i <= q; i++){
        string p;
        cin >> p;
        if (p == "query"){
            queries[i].type = 0;
            cin >> queries[i].a >> queries[i].b;
            queries[i].b--;
        } else {
            queries[i].type = 1;
            cin >> queries[i].a;
        }
    }

    cur = s;
    set<int> empPos;
    for(int i = 1; i <= n; i++){
        last[i] = 0;
        if (cur[i] == '0')
            empPos.insert(i);
    }
    empPos.insert(0);
    empPos.insert(n + 1);
    for(int i = 1; i <= q; i++){
        if (queries[i].type == 0){
            bit.fakeQuery(queries[i].a, queries[i].b);
        } else {
            int pos = queries[i].a;
            if (cur[pos] == '0'){
                empPos.erase(pos);
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= pos - 1){
                    bit.fakeUpdate(l + 1, l + 1);
                    bit.fakeUpdate(l + 1, pos);
                }
                if (pos + 1 <= r - 1)
                    bit.fakeUpdate(pos + 1, pos + 1);
                    bit.fakeUpdate(pos + 1, r);
                cur[pos] = '1';
            } else {
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= r - 1)
                    bit.fakeUpdate(l + 1, r - 1);
                empPos.insert(pos);
                cur[pos] = '0';
            }
        }
    }

    bit.normalize();
    cur = s;
    empPos.clear();
    for(int i = 1; i <= n; i++){
        last[i] = 0;
        if (cur[i] == '0')
            empPos.insert(i);
    }
    empPos.insert(0);
    empPos.insert(n + 1);
    for(int i = 1; i <= q; i++){
        if (queries[i].type == 0){
            int res = bit.query(queries[i].a, queries[i].b);
            auto it = empPos.lower_bound(queries[i].a);
            if (*it > queries[i].b)
                res += (i - last[*(--it) + 1]);
            cout << res << '\n';
        } else {
            int pos = queries[i].a;
            if (cur[pos] == '0'){
                empPos.erase(pos);
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= pos - 1){
                    int num = i - last[l + 1];
                    bit.update(l + 1, l + 1, num);
                    bit.update(l + 1, pos, -num);
                    last[l + 1] = i;
                }
                if (pos + 1 <= r - 1){
                    int num = i - last[pos + 1];
                    bit.update(pos + 1, pos + 1, num);
                    bit.update(pos + 1, r, -num);
                    last[pos + 1] = i;
                }
                cur[pos] = '1';
                last[pos] = i;
            } else {
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= r - 1){
                    int num = i - last[l + 1];
                    bit.update(l + 1, l + 1, num);
                    bit.update(l + 1, r, -num);
                    last[l + 1] = i;
                }
                last[pos + 1] = i;
                empPos.insert(pos);
                cur[pos] = '0';
            }
        }
    }

    return 0;
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:93:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   93 |                 if (pos + 1 <= r - 1)
      |                 ^~
street_lamps.cpp:95:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   95 |                     bit.fakeUpdate(pos + 1, r);
      |                     ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23756 KB Output is correct
2 Correct 26 ms 23756 KB Output is correct
3 Correct 25 ms 23792 KB Output is correct
4 Correct 25 ms 23736 KB Output is correct
5 Correct 25 ms 23764 KB Output is correct
6 Correct 31 ms 23812 KB Output is correct
7 Correct 25 ms 23756 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 47820 KB Output is correct
2 Correct 664 ms 51300 KB Output is correct
3 Correct 960 ms 53008 KB Output is correct
4 Correct 2147 ms 75356 KB Output is correct
5 Correct 2242 ms 83272 KB Output is correct
6 Correct 2172 ms 75524 KB Output is correct
7 Correct 1494 ms 72912 KB Output is correct
8 Correct 1035 ms 60164 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24140 KB Output is correct
2 Correct 32 ms 24124 KB Output is correct
3 Correct 27 ms 23988 KB Output is correct
4 Correct 26 ms 23796 KB Output is correct
5 Correct 2790 ms 100168 KB Output is correct
6 Correct 2660 ms 93152 KB Output is correct
7 Correct 2194 ms 79652 KB Output is correct
8 Correct 1060 ms 56016 KB Output is correct
9 Correct 168 ms 30796 KB Output is correct
10 Correct 177 ms 31408 KB Output is correct
11 Correct 192 ms 31656 KB Output is correct
12 Correct 1589 ms 68748 KB Output is correct
13 Correct 1045 ms 55896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23876 KB Output is correct
2 Correct 27 ms 23872 KB Output is correct
3 Correct 34 ms 23968 KB Output is correct
4 Correct 29 ms 24040 KB Output is correct
5 Correct 1396 ms 61748 KB Output is correct
6 Correct 1703 ms 66956 KB Output is correct
7 Correct 2078 ms 70644 KB Output is correct
8 Correct 2622 ms 72136 KB Output is correct
9 Correct 851 ms 53536 KB Output is correct
10 Correct 859 ms 64240 KB Output is correct
11 Correct 859 ms 57120 KB Output is correct
12 Correct 863 ms 64228 KB Output is correct
13 Correct 859 ms 56984 KB Output is correct
14 Correct 868 ms 63988 KB Output is correct
15 Correct 1526 ms 74628 KB Output is correct
16 Correct 1096 ms 61892 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23756 KB Output is correct
2 Correct 26 ms 23756 KB Output is correct
3 Correct 25 ms 23792 KB Output is correct
4 Correct 25 ms 23736 KB Output is correct
5 Correct 25 ms 23764 KB Output is correct
6 Correct 31 ms 23812 KB Output is correct
7 Correct 25 ms 23756 KB Output is correct
8 Correct 576 ms 47820 KB Output is correct
9 Correct 664 ms 51300 KB Output is correct
10 Correct 960 ms 53008 KB Output is correct
11 Correct 2147 ms 75356 KB Output is correct
12 Correct 2242 ms 83272 KB Output is correct
13 Correct 2172 ms 75524 KB Output is correct
14 Correct 1494 ms 72912 KB Output is correct
15 Correct 1035 ms 60164 KB Output is correct
16 Correct 32 ms 24140 KB Output is correct
17 Correct 32 ms 24124 KB Output is correct
18 Correct 27 ms 23988 KB Output is correct
19 Correct 26 ms 23796 KB Output is correct
20 Correct 2790 ms 100168 KB Output is correct
21 Correct 2660 ms 93152 KB Output is correct
22 Correct 2194 ms 79652 KB Output is correct
23 Correct 1060 ms 56016 KB Output is correct
24 Correct 168 ms 30796 KB Output is correct
25 Correct 177 ms 31408 KB Output is correct
26 Correct 192 ms 31656 KB Output is correct
27 Correct 1589 ms 68748 KB Output is correct
28 Correct 1045 ms 55896 KB Output is correct
29 Correct 31 ms 23876 KB Output is correct
30 Correct 27 ms 23872 KB Output is correct
31 Correct 34 ms 23968 KB Output is correct
32 Correct 29 ms 24040 KB Output is correct
33 Correct 1396 ms 61748 KB Output is correct
34 Correct 1703 ms 66956 KB Output is correct
35 Correct 2078 ms 70644 KB Output is correct
36 Correct 2622 ms 72136 KB Output is correct
37 Correct 851 ms 53536 KB Output is correct
38 Correct 859 ms 64240 KB Output is correct
39 Correct 859 ms 57120 KB Output is correct
40 Correct 863 ms 64228 KB Output is correct
41 Correct 859 ms 56984 KB Output is correct
42 Correct 868 ms 63988 KB Output is correct
43 Correct 1526 ms 74628 KB Output is correct
44 Correct 1096 ms 61892 KB Output is correct
45 Correct 280 ms 41012 KB Output is correct
46 Correct 407 ms 41052 KB Output is correct
47 Correct 1266 ms 52516 KB Output is correct
48 Correct 2140 ms 74512 KB Output is correct
49 Correct 201 ms 35764 KB Output is correct
50 Correct 197 ms 35252 KB Output is correct
51 Correct 210 ms 35856 KB Output is correct
52 Correct 246 ms 38032 KB Output is correct
53 Correct 244 ms 38040 KB Output is correct
54 Correct 267 ms 38116 KB Output is correct