oj.uz

Submission #354151

# Submission time Handle Problem Language Result Execution time Memory
354151 2021-01-21T13:30:00 Z parsabahrami Street Lamps (APIO19_street_lamps) C++17
20 / 100
 3901 ms 137488 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], 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] = 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;
    }
    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++) {
        auto it = st.upper_bound({{i, MOD}, 0});
        if (it != st.begin()) {
            it--;
            if (it->F.F <= i && it->F.S >= i) A[i] = 1;
            else A[i] = 0;
        }
    }
    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 109 ms 47340 KB Output is correct
2 Correct 108 ms 47468 KB Output is correct
3 Correct 127 ms 47340 KB Output is correct
4 Correct 113 ms 47340 KB Output is correct
5 Correct 108 ms 47340 KB Output is correct
6 Correct 110 ms 47340 KB Output is correct
7 Correct 108 ms 47340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 90200 KB Output is correct
2 Incorrect 1208 ms 88240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 47596 KB Output is correct
2 Correct 122 ms 47724 KB Output is correct
3 Correct 121 ms 47688 KB Output is correct
4 Correct 108 ms 47340 KB Output is correct
5 Correct 3797 ms 137488 KB Output is correct
6 Correct 3483 ms 129036 KB Output is correct
7 Correct 2621 ms 116428 KB Output is correct
8 Correct 407 ms 60232 KB Output is correct
9 Correct 267 ms 54124 KB Output is correct
10 Incorrect 284 ms 54508 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 47340 KB Output is correct
2 Correct 109 ms 47468 KB Output is correct
3 Correct 119 ms 47596 KB Output is correct
4 Correct 117 ms 47724 KB Output is correct
5 Correct 689 ms 69228 KB Output is correct
6 Correct 1751 ms 89808 KB Output is correct
7 Correct 2682 ms 111764 KB Output is correct
8 Correct 3901 ms 133436 KB Output is correct
9 Correct 1560 ms 111016 KB Output is correct
10 Correct 1768 ms 128556 KB Output is correct
11 Correct 1584 ms 110836 KB Output is correct
12 Incorrect 1775 ms 128608 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 47340 KB Output is correct
2 Correct 108 ms 47468 KB Output is correct
3 Correct 127 ms 47340 KB Output is correct
4 Correct 113 ms 47340 KB Output is correct
5 Correct 108 ms 47340 KB Output is correct
6 Correct 110 ms 47340 KB Output is correct
7 Correct 108 ms 47340 KB Output is correct
8 Correct 1079 ms 90200 KB Output is correct
9 Incorrect 1208 ms 88240 KB Output isn't correct
10 Halted 0 ms 0 KB -