oj.uz

Submission #354154

# Submission time Handle Problem Language Result Execution time Memory
354154 2021-01-21T13:40:31 Z parsabahrami Street Lamps (APIO19_street_lamps) C++17
100 / 100
 3798 ms 134012 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 3e5 + 10, MOD = 1e9 + 7;
vector<int> F[N], vec[N]; set<pair<pii, int>> st, tmp;
int n, q, A[N], T[N], type[N], ql[N], qr[N]; char C[N];

void __init(int r, int c) {
    for (; r < N; r += r & -r) vec[r].push_back(c);
}

void init(int r, int c) {
    __init(r, r), __init(c + 1, c + 1), __init(r, c + 1), __init(c + 1, r);
}

void __upd(int r, int c, int x) {
    for (; r < N; r += r & -r) {
        int _c = lower_bound(vec[r].begin(), vec[r].end(), c) - vec[r].begin(); 
        for (; _c < SZ(F[r]); _c += _c & -_c) F[r][_c] += x;
    }
}

void upd(int r, int c, int x) {
    __upd(r, r, x), __upd(c + 1, c + 1, x), __upd(r, c + 1, -x), __upd(c + 1, r, -x);
}

int get(int r, int c) {
    int ret = 0;
    for (; r; r -= r & -r) {
        int _c = upper_bound(vec[r].begin(), vec[r].end(), c) - vec[r].begin() - 1;
        for (; _c; _c -= _c & -_c) ret += F[r][_c];
    }
    return ret;
}

void __erase(int x) {
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it == st.begin()) return;
    it--;
    int l = it->F.F, r = it->F.S;
    init(l, r); st.erase(it);
    if (x > l) st.insert({{l, x - 1}, 0});
    if (x < r) st.insert({{x + 1, r}, 0});
}

void __add(int x) {
    int l = x, r = x;
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it != st.end()) {
        if (it->F.F == x + 1) {
            init(x + 1, it->F.S); r = it->F.S, st.erase(it);
        }
    }
    it = st.upper_bound({{x, MOD}, 0}); 
    if (it != st.begin()) {
        it--;
        if (it->F.S == x - 1) {
            init(it->F.F, x - 1); l = it->F.F, st.erase(it);
        }
    }
    st.insert({{l, r}, 0});
}

void add(int x, int id) {
    int l = x, r = x;
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it != st.end()) {
        if (it->F.F == x + 1) {
            upd(x + 1, it->F.S, id - it->S), r = it->F.S, st.erase(it);
        }
    }
    it = st.upper_bound({{x, MOD}, 0}); 
    if (it != st.begin()) {
        it--;
        if (it->F.S == x - 1) {
            upd(it->F.F, x - 1, id - it->S), l = it->F.F, st.erase(it);
        }
    }
    st.insert({{l, r}, id});
}

void erase(int x, int id) {
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it == st.begin()) return;
    it--;
    int l =it->F.F, r = it->F.S;
    upd(l, r, id - it->S); st.erase(it);
    if (x > l) st.insert({{l, x - 1}, id});
    if (x < r) st.insert({{x + 1, r}, id});
}

int main() {
    scanf("%d%d\n%s", &n, &q, C + 1);
    for (int i = 1; i <= n; i++) A[i] = T[i] = C[i] - '0';
    for (int i = 1; i <= n; i++) {
        if (!A[i]) continue;
        int j = i; 
        while (j <= n && A[j]) j++;
        st.insert({{i, j - 1}, 0});
        i = j - 1;
    }
    tmp = st;
    for (int i = 1; i <= q; i++) {
        string t; cin >> t;
        type[i] = (t == "toggle");
        if (type[i]) {
            scanf("%d", &ql[i]);
            if (A[ql[i]]) {
               __erase(ql[i]);
            } else {
               __add(ql[i]);
            }
            A[ql[i]] ^= 1;
        } else {
            scanf("%d%d", &ql[i], &qr[i]);
        }
    }
    for (int i = 0; i < N; i++) {
        vec[i].push_back(0);
        sort(vec[i].begin(), vec[i].end()); 
        vec[i].resize(unique(vec[i].begin(), vec[i].end()) - vec[i].begin());
        while (SZ(F[i]) < SZ(vec[i]) + 10) F[i].push_back(0);
    } 
    st = tmp;
    for (int i = 1; i <= n; i++) {
        A[i] = T[i];
    }
    for (int i = 1; i <= q; i++) {
        if (type[i]) {
            if (A[ql[i]]) erase(ql[i], i);
            else add(ql[i], i);
            A[ql[i]] ^= 1;
        } else {
            int x = get(ql[i], qr[i] - 1);
            auto it = st.upper_bound({{ql[i], MOD}, 0});
            if (it != st.begin()) {
                it--; 
                if (it->F.S >= qr[i] - 1) x += i - it->S;
            }
            printf("%d\n", x);
        }
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d%d\n%s", &n, &q, C + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |             scanf("%d", &ql[i]);
      |             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:125:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |             scanf("%d%d", &ql[i], &qr[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 47372 KB Output is correct
2 Correct 110 ms 47368 KB Output is correct
3 Correct 109 ms 47340 KB Output is correct
4 Correct 111 ms 47340 KB Output is correct
5 Correct 110 ms 47340 KB Output is correct
6 Correct 109 ms 47340 KB Output is correct
7 Correct 109 ms 47340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1070 ms 90280 KB Output is correct
2 Correct 1190 ms 88088 KB Output is correct
3 Correct 1510 ms 89660 KB Output is correct
4 Correct 2403 ms 105456 KB Output is correct
5 Correct 2657 ms 117924 KB Output is correct
6 Correct 2625 ms 113108 KB Output is correct
7 Correct 408 ms 60012 KB Output is correct
8 Correct 407 ms 61524 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 47852 KB Output is correct
2 Correct 135 ms 47808 KB Output is correct
3 Correct 130 ms 47852 KB Output is correct
4 Correct 113 ms 47340 KB Output is correct
5 Correct 3769 ms 134012 KB Output is correct
6 Correct 3442 ms 125244 KB Output is correct
7 Correct 2618 ms 112160 KB Output is correct
8 Correct 403 ms 55440 KB Output is correct
9 Correct 272 ms 51392 KB Output is correct
10 Correct 280 ms 51436 KB Output is correct
11 Correct 280 ms 54636 KB Output is correct
12 Correct 395 ms 60140 KB Output is correct
13 Correct 447 ms 61576 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 47332 KB Output is correct
2 Correct 112 ms 47568 KB Output is correct
3 Correct 124 ms 47596 KB Output is correct
4 Correct 120 ms 47724 KB Output is correct
5 Correct 681 ms 64108 KB Output is correct
6 Correct 1697 ms 85564 KB Output is correct
7 Correct 2551 ms 107860 KB Output is correct
8 Correct 3798 ms 130196 KB Output is correct
9 Correct 1592 ms 107764 KB Output is correct
10 Correct 1763 ms 125964 KB Output is correct
11 Correct 1574 ms 107508 KB Output is correct
12 Correct 1731 ms 125528 KB Output is correct
13 Correct 1561 ms 110908 KB Output is correct
14 Correct 1764 ms 128452 KB Output is correct
15 Correct 392 ms 60140 KB Output is correct
16 Correct 398 ms 61464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 47372 KB Output is correct
2 Correct 110 ms 47368 KB Output is correct
3 Correct 109 ms 47340 KB Output is correct
4 Correct 111 ms 47340 KB Output is correct
5 Correct 110 ms 47340 KB Output is correct
6 Correct 109 ms 47340 KB Output is correct
7 Correct 109 ms 47340 KB Output is correct
8 Correct 1070 ms 90280 KB Output is correct
9 Correct 1190 ms 88088 KB Output is correct
10 Correct 1510 ms 89660 KB Output is correct
11 Correct 2403 ms 105456 KB Output is correct
12 Correct 2657 ms 117924 KB Output is correct
13 Correct 2625 ms 113108 KB Output is correct
14 Correct 408 ms 60012 KB Output is correct
15 Correct 407 ms 61524 KB Output is correct
16 Correct 120 ms 47852 KB Output is correct
17 Correct 135 ms 47808 KB Output is correct
18 Correct 130 ms 47852 KB Output is correct
19 Correct 113 ms 47340 KB Output is correct
20 Correct 3769 ms 134012 KB Output is correct
21 Correct 3442 ms 125244 KB Output is correct
22 Correct 2618 ms 112160 KB Output is correct
23 Correct 403 ms 55440 KB Output is correct
24 Correct 272 ms 51392 KB Output is correct
25 Correct 280 ms 51436 KB Output is correct
26 Correct 280 ms 54636 KB Output is correct
27 Correct 395 ms 60140 KB Output is correct
28 Correct 447 ms 61576 KB Output is correct
29 Correct 113 ms 47332 KB Output is correct
30 Correct 112 ms 47568 KB Output is correct
31 Correct 124 ms 47596 KB Output is correct
32 Correct 120 ms 47724 KB Output is correct
33 Correct 681 ms 64108 KB Output is correct
34 Correct 1697 ms 85564 KB Output is correct
35 Correct 2551 ms 107860 KB Output is correct
36 Correct 3798 ms 130196 KB Output is correct
37 Correct 1592 ms 107764 KB Output is correct
38 Correct 1763 ms 125964 KB Output is correct
39 Correct 1574 ms 107508 KB Output is correct
40 Correct 1731 ms 125528 KB Output is correct
41 Correct 1561 ms 110908 KB Output is correct
42 Correct 1764 ms 128452 KB Output is correct
43 Correct 392 ms 60140 KB Output is correct
44 Correct 398 ms 61464 KB Output is correct
45 Correct 591 ms 78636 KB Output is correct
46 Correct 739 ms 77244 KB Output is correct
47 Correct 1538 ms 82252 KB Output is correct
48 Correct 2391 ms 104956 KB Output is correct
49 Correct 292 ms 55020 KB Output is correct
50 Correct 300 ms 55020 KB Output is correct
51 Correct 293 ms 55148 KB Output is correct
52 Correct 295 ms 55532 KB Output is correct
53 Correct 292 ms 55660 KB Output is correct
54 Correct 294 ms 55404 KB Output is correct