Submission #558192

#	Time	Username	Problem	Language	Result	Execution time	Memory
558192		hoanghq2004	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	102 ms	29204 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 = 3e3 + 10;

int n, q;
int s[N][N];

void add(int x, int y, int u, int v, int d) {
//    cout << x << ' ' << y << ' ' << u << ' ' << v << " aa " << d << '\n';
    for (int i = x; i <= y; ++i)
        for (int j = u; j <= v; ++j)
            s[i][j] += d;
}

int get(int x, int y) {
    return s[x][y];
}

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;
                add(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;
                add(L, i, i, R, - T);
            }
        } else {
            int L, R;
            cin >> L >> R;
            --R;
            int cur = get(L, R);
            auto iter = s.lower_bound(L);
            if (iter == s.end() || *iter > R) cur += T;
            cout << cur << '\n';
        }
    }
}

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