Submission #558219

#	Time	Username	Problem	Language	Result	Execution time	Memory
558219		hoanghq2004	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2674 ms	109664 KiB

street_lamps

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

int n, q;
struct Query {
    int x, y, u, v, d, type;
};

vector <Query> work;
vector <int> fake[N], BIT[N];

void add_fake(int x, int y) {
    for (; x < N; x += x & - x)
        fake[x].push_back(y);
}

void add(int x, int y, int d) {
    for (; x < N; x += x & - x) {
        int t = lower_bound(fake[x].begin(), fake[x].end(), y) - fake[x].begin() + 1;
        for (; t < BIT[x].size(); t += t & - t) BIT[x][t] += d;
    }
}

int get(int x, int y) {
    int ans = 0;
    for (; x; x -= x & - x) {
        int t = upper_bound(fake[x].begin(), fake[x].end(), y) - fake[x].begin();
        for (; t; t -= t & - t)
            ans += BIT[x][t];
    }
    return ans;
}

void add(int x, int y, int u, int v, int d) {
    add(x, u, d);
    add(y + 1, u, - d);
    add(x, v + 1, - d);
    add(y + 1, v + 1, d);
}

void push(int x, int y, int u, int v, int d) {
    work.push_back({x, y, u, v, d, 0});
    add_fake(x, u);
    add_fake(y + 1, u);
    add_fake(x, v + 1);
    add_fake(y + 1, v + 1);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    set <int> s;
    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;
        if (c == '0') s.insert(i);
    }
    for (int T = 1; T <= q; ++T) {
        string cmd;
        cin >> cmd;
        if (cmd == "toggle") {
            int i;
            cin >> i;
            int L = 1, R = n;
            if (s.find(i) == s.end()) {
                auto iter = s.lower_bound(i);
                if (iter != s.end()) R = *iter - 1;
                if (iter != s.begin()) L = *(--iter) + 1;
                push(L, i, i, R, T);
                s.insert(i);
            } else {
                s.erase(i);
                auto iter = s.lower_bound(i);
                if (iter != s.end()) R = *iter - 1;
                if (iter != s.begin()) L = *(--iter) + 1;
                push(L, i, i, R, - T);
            }
        } else {
            int L, R;
            cin >> L >> R;
            --R;
            int cur = 0;
            auto iter = s.lower_bound(L);
            if (iter == s.end() || *iter > R) cur += T;
            work.push_back({L, R, L, R, cur, 1});
        }
    }
    for (int i = 0; i < N; ++i) {
        sort(fake[i].begin(), fake[i].end());
        fake[i].erase(unique(fake[i].begin(), fake[i].end()), fake[i].end());
        BIT[i].assign(fake[i].size() + 5, 0);
    }
    for (auto [x, y, u, v, d, type]: work) {
        if (type == 0) {
            add(x, y, u, v, d);
        } else {
            cout << d + get(x, y) << '\n';
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (; t < BIT[x].size(); t += t & - t) BIT[x][t] += d;
      |                ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:104:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |     for (auto [x, y, u, v, d, type]: work) {
      |               ^

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20