oj.uz

Submission #1035194

# Submission time Handle Problem Language Result Execution time Memory
1035194 2024-07-26T06:17:25 Z stdfloat Street Lamps (APIO19_street_lamps) C++17
20 / 100
 432 ms 36292 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

vector<int> st, lz;

void LZ(int nd, int l, int r) {
    st[nd] += lz[nd];

    if (l != r) {
        int ch = (nd << 1) + 1;
        lz[ch] += lz[nd];
        lz[ch + 1] += lz[nd];
    }

    lz[nd] = 0;
}

int upd(int nd, int l, int r, int x, int y, int vl) {
    LZ(nd, l, r);
    
    if (y < l || r < x) return st[nd];

    if (x <= l && r <= y) {
        lz[nd] = vl; LZ(nd, l, r);
        return st[nd];
    }

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return st[nd] = upd(ch, l, md, x, y, vl) + upd(ch + 1, md + 1, r, x, y, vl);
}

int fnd(int nd, int l, int r, int x) {
    LZ(nd, l, r);

    if (r < x || x < l) return 0;

    if (l == r) return st[nd];

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return fnd(ch, l, md, x) + fnd(ch + 1, md + 1, r, x);
}

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

    int n, q;
    string s;
    cin >> n >> q >> s;

    set<int> zr = {-1, n};
    vector<pair<pii, pii>> v;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') zr.insert(i);
        else {
            int r = i;
            while (r + 1 < n && s[r + 1] == '1') r++;

            v.push_back({{i, -1}, {i, r}});
            v.push_back({{r + 1, 1}, {i, r}});

            i = r;
        }
    }

    bool tr = false;
    for (int z = 2; z <= q + 1; z++) {
        string t;
        cin >> t;

        if (t == "toggle") {
            int i;
            cin >> i; i--;

            int l = *--zr.lower_bound(i), r = *zr.upper_bound(i);
            if (s[i] == '0') {
                zr.erase(i);
                s[i] = '1';
                v.push_back({{l + 1, -z}, {i, r - 1}});
                v.push_back({{i + 1, z}, {i, r - 1}});
            }
            else {
                s[i] = '0';
                zr.insert(i);
                v.push_back({{l + 1, z}, {i, r - 1}});
                v.push_back({{i + 1, -z}, {i, r - 1}});
            }
        }
        else {
            int a, b;
            cin >> a >> b; a--; b--;

            v.push_back({{a, (int)1e8 + z}, {b, z}});
        }
    }

    sort(v.begin(), v.end());
    
    st.assign(n << 2, 0);
    lz.assign(n << 2, 0);
    vector<int> ans(q + 2, -1);
    for (auto i : v) {
        if (i.ff.ss <= (int)1e8) upd(0, 0, n - 1, i.ss.ff, i.ss.ss, i.ff.ss);
        else ans[i.ff.ss - (int)1e8] = fnd(0, 0, n - 1, i.ss.ff - 1) + (i.ss.ff <= *zr.lower_bound(i.ff.ff) ? i.ss.ss : 0);
    }

    for (auto i : ans) if (i != -1) cout << i << '\n';
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:71:10: warning: unused variable 'tr' [-Wunused-variable]
   71 |     bool tr = false;
      |          ^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 12716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 247 ms 31564 KB Output is correct
6 Correct 334 ms 32604 KB Output is correct
7 Correct 370 ms 33200 KB Output is correct
8 Correct 432 ms 33988 KB Output is correct
9 Correct 167 ms 13236 KB Output is correct
10 Correct 163 ms 19604 KB Output is correct
11 Correct 162 ms 13120 KB Output is correct
12 Correct 162 ms 19636 KB Output is correct
13 Correct 172 ms 13240 KB Output is correct
14 Correct 168 ms 19636 KB Output is correct
15 Correct 234 ms 36292 KB Output is correct
16 Correct 151 ms 23752 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -