Submission #768476

#	Time	Username	Problem	Language	Result	Execution time	Memory
768476		pandapythoner	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2365 ms	161640 KiB

street_lamps

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20