oj.uz

Submission #768476

# Submission time Handle Problem Language Result Execution time Memory
768476 2023-06-28T07:49:19 Z pandapythoner Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2365 ms 161640 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

struct Fenw {
    int n;
    vector<int> t;

    void build(int _n) {
        n = _n;
        t.assign(n + 1, 0);
    }

    void add(int i, int x) {
        i += 1;
        while (i <= n) {
            t[i] += x;
            i = (i | (i - 1)) + 1;
        }
    }

    int get(int i) {
        int rs = 0;
        i += 1;
        while (i > 0) {
            rs += t[i];
            i = (i & (i - 1));
        }
        return rs;
    }
};

struct SGT {
    int n;
    vector<vector<int>> poss;
    vector<Fenw> t;

    void build(int v, int tl, int tr, vector<vector<int>> &a) {
        if (tl == tr) {
            poss[v] = a[tl];
            sort(all(poss[v]));
            t[v].build(poss[v].size());
            return;
        }
        int tm = (tl + tr) / 2;
        build(v + v, tl, tm, a);
        build(v + v + 1, tm + 1, tr, a);
        poss[v].resize(poss[v + v].size() + poss[v + v + 1].size());
        merge(all(poss[v + v]), all(poss[v + v + 1]), poss[v].begin());
        t[v].build(poss[v].size());
    }

    void build(vector<vector<int>> &a) {
        n = a.size();
        poss.resize(n * 4);
        t.resize(n * 4);
        build(1, 0, n - 1, a);
    }

    void add(int v, int tl, int tr, int i, int j, int x) {
        if (tr < i || i < tl) {
            return;
        }
        t[v].add(lower_bound(all(poss[v]), j) - poss[v].begin(), x);
        if (tl == tr) {
            return;
        }
        int tm = (tl + tr) / 2;
        add(v + v, tl, tm, i, j, x);
        add(v + v + 1, tm + 1, tr, i, j, x);
    }

    void add(int i, int j, int x) {
        add(1, 0, n - 1, i, j, x);
    }

    int get(int v, int tl, int tr, int i, int j) {
        if (i < tl) {
            return 0;
        }
        if (tr <= i) {
            return t[v].get(upper_bound(all(poss[v]), j) - poss[v].begin() - 1);
        }
        int tm = (tl + tr) / 2;
        return get(v + v, tl, tm, i, j) + get(v + v + 1, tm + 1, tr, i, j);
    }

    int get(int i, int j) {
        return get(1, 0, n - 1, i, j);
    }
};

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i += 1) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }
    vector<array<int, 3>> q(m);
    for (int i = 0; i < m; i += 1) {
        string s;
        int x, y, z;
        cin >> s;
        x = (int)(s == "toggle");
        cin >> y;
        --y;
        if (x == 0) {
            cin >> z;
            --z;
            --z;
        }
        q[i] = {x, y, z};
    }
    SGT sgt;
    vector<vector<int>> d(n);
    map<pair<int, int>, int> mp;
    for (int itr = 0; itr < 2; itr += 1) {
        mp.clear();
        vector<int> b = a;
        int lstone = 0;
        for (int i = 0; i < n; i += 1) {
            if (b[i] == 0) {
                lstone = i + 1;
            } else {
                if (i + 1 == n || b[i + 1] == 0) {
                    mp[make_pair(lstone, i)] = -1;
                }
            }
        }
        for (int i = 0; i < m; i += 1) {
            if (q[i][0] == 1) {
                int j = q[i][1];
                vector<array<int, 3>> to_add;
                if (b[j] == 0) {
                    int l = j;
                    int r = j;
                    auto it = mp.lower_bound(make_pair(j, j));
                    if (it != mp.begin()) {
                        auto nit = prev(it);
                        if (nit->first.second == j - 1) {
                            to_add.push_back({nit->first.first, nit->first.second, i - nit->second});
                            l = nit->first.first;
                            mp.erase(nit);
                        }
                    }
                    if (it != mp.end()) {
                        auto nit = it;
                        if (nit->first.first == j + 1) {
                            to_add.push_back({nit->first.first, nit->first.second, i - nit->second});
                            r = nit->first.second;
                            mp.erase(nit);
                        }
                    }
                    mp[make_pair(l, r)] = i;
                } else {
                    auto it = prev(mp.lower_bound(make_pair(j + 1, j + 1)));
                    to_add.push_back({it->first.first, it->first.second, i - it->second});
                    int l = it->first.first;
                    int r = it->first.second;
                    mp.erase(it);
                    if (l != j) {
                        mp[make_pair(l, j - 1)] = i;
                    }
                    if (r != j) {
                        mp[make_pair(j + 1, r)] = i;
                    }
                }
                b[j] ^= 1;
                for (auto [x, y, z] : to_add) {
                    if (itr == 0) {
                        d[x].push_back(-y);
                    } else {
                        sgt.add(x, -y, z);
                    }
                }
            } else {
                if (itr == 1) {
                    int l = q[i][1];
                    int r = q[i][2];
                    int rs = 0;
                    auto it = mp.lower_bound(make_pair(l + 1, l + 1));
                    if (it != mp.begin()) {
                        --it;
                        if (it->first.first <= l && r <= it->first.second) {
                            rs += i - it->second;
                        }
                    }
                    rs += sgt.get(l, -r);
                    cout << rs << "\n";
                }
            }
        }
        if (itr == 1) {
            break;
        }
        sgt.build(d);
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:182:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  182 |                 for (auto [x, y, z] : to_add) {
      |                           ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 17876 KB Output is correct
2 Correct 375 ms 20108 KB Output is correct
3 Correct 654 ms 27120 KB Output is correct
4 Correct 1379 ms 138432 KB Output is correct
5 Correct 1528 ms 144412 KB Output is correct
6 Correct 1485 ms 143284 KB Output is correct
7 Correct 233 ms 104280 KB Output is correct
8 Correct 229 ms 105732 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2214 ms 161640 KB Output is correct
6 Correct 1950 ms 157612 KB Output is correct
7 Correct 1509 ms 143712 KB Output is correct
8 Correct 231 ms 105676 KB Output is correct
9 Correct 66 ms 6860 KB Output is correct
10 Correct 90 ms 7392 KB Output is correct
11 Correct 78 ms 7760 KB Output is correct
12 Correct 220 ms 104244 KB Output is correct
13 Correct 217 ms 105732 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 401 ms 109940 KB Output is correct
6 Correct 867 ms 128068 KB Output is correct
7 Correct 1417 ms 142752 KB Output is correct
8 Correct 2365 ms 161116 KB Output is correct
9 Correct 543 ms 25720 KB Output is correct
10 Correct 439 ms 26356 KB Output is correct
11 Correct 524 ms 25744 KB Output is correct
12 Correct 405 ms 26396 KB Output is correct
13 Correct 526 ms 25712 KB Output is correct
14 Correct 429 ms 26384 KB Output is correct
15 Correct 233 ms 104296 KB Output is correct
16 Correct 218 ms 105656 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 270 ms 17876 KB Output is correct
9 Correct 375 ms 20108 KB Output is correct
10 Correct 654 ms 27120 KB Output is correct
11 Correct 1379 ms 138432 KB Output is correct
12 Correct 1528 ms 144412 KB Output is correct
13 Correct 1485 ms 143284 KB Output is correct
14 Correct 233 ms 104280 KB Output is correct
15 Correct 229 ms 105732 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2214 ms 161640 KB Output is correct
21 Correct 1950 ms 157612 KB Output is correct
22 Correct 1509 ms 143712 KB Output is correct
23 Correct 231 ms 105676 KB Output is correct
24 Correct 66 ms 6860 KB Output is correct
25 Correct 90 ms 7392 KB Output is correct
26 Correct 78 ms 7760 KB Output is correct
27 Correct 220 ms 104244 KB Output is correct
28 Correct 217 ms 105732 KB Output is correct
29 Correct 1 ms 588 KB Output is correct
30 Correct 2 ms 724 KB Output is correct
31 Correct 2 ms 724 KB Output is correct
32 Correct 2 ms 712 KB Output is correct
33 Correct 401 ms 109940 KB Output is correct
34 Correct 867 ms 128068 KB Output is correct
35 Correct 1417 ms 142752 KB Output is correct
36 Correct 2365 ms 161116 KB Output is correct
37 Correct 543 ms 25720 KB Output is correct
38 Correct 439 ms 26356 KB Output is correct
39 Correct 524 ms 25744 KB Output is correct
40 Correct 405 ms 26396 KB Output is correct
41 Correct 526 ms 25712 KB Output is correct
42 Correct 429 ms 26384 KB Output is correct
43 Correct 233 ms 104296 KB Output is correct
44 Correct 218 ms 105656 KB Output is correct
45 Correct 93 ms 8876 KB Output is correct
46 Correct 165 ms 11640 KB Output is correct
47 Correct 579 ms 55780 KB Output is correct
48 Correct 1306 ms 138112 KB Output is correct
49 Correct 78 ms 7884 KB Output is correct
50 Correct 76 ms 7920 KB Output is correct
51 Correct 77 ms 8048 KB Output is correct
52 Correct 96 ms 8560 KB Output is correct
53 Correct 85 ms 8552 KB Output is correct
54 Correct 81 ms 8456 KB Output is correct