oj.uz

Submission #1035192

# Submission time Handle Problem Language Result Execution time Memory
1035192 2024-07-26T06:15:10 Z stdfloat Street Lamps (APIO19_street_lamps) C++17
0 / 100
 5000 ms 36700 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({{i + 1, 1}, {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:69:10: warning: unused variable 'tr' [-Wunused-variable]
   69 |     bool tr = false;
      |          ^~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
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 326 ms 34148 KB Output is correct
6 Correct 386 ms 34992 KB Output is correct
7 Correct 432 ms 35700 KB Output is correct
8 Correct 505 ms 36700 KB Output is correct
9 Correct 177 ms 13128 KB Output is correct
10 Correct 177 ms 19432 KB Output is correct
11 Correct 170 ms 13188 KB Output is correct
12 Correct 172 ms 19476 KB Output is correct
13 Correct 173 ms 13236 KB Output is correct
14 Correct 173 ms 19468 KB Output is correct
15 Correct 249 ms 36552 KB Output is correct
16 Execution timed out 5097 ms 3344 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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