Submission #926279

#	Time	Username	Problem	Language	Result	Execution time	Memory
926279		TAhmed33	Street Lamps (APIO19_street_lamps)	C++98	20 / 100	5085 ms	19236 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
/*struct Implicit {
    vector <int> tree, tl, tr; int cnt;
    int create () {
        ++cnt; tl.push_back(-1); tr.push_back(-1); tree.push_back(0); return cnt;
    }
    void init () {
        tree.push_back(0); tl.push_back(-1); tr.push_back(-1); cnt = 0;
    }
    void update (int l, int r, int a, int b, int node) {
        if (l == r) {
            tree[node] += b; return;
        }
        int mid = (l + r) >> 1;
        if (a <= mid) {
            if (tl[node] == -1) tl[node] = create();
            else tree[node] -= tree[tl[node]];
            update(l, mid, a, b, tl[node]);
            tree[node] += tree[tl[node]];
        } else {
            if (tr[node] == -1) tr[node] = create();
            else tree[node] -= tree[tr[node]];
            update(mid + 1, r, a, b, tr[node]);
            tree[node] += tree[tr[node]];
        }
    }
    int get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return 0;
        if (l >= a && r <= b) return tree[node];
        int sum = 0, mid = (l + r) >> 1;
        if (tl[node] != -1) sum += get(l, mid, a, b, tl[node]);
        if (tr[node] != -1) sum += get(mid + 1, r, a, b, tr[node]);
        return sum;
    }
};*/
typedef long long ll;
const int MAXN = 3e5 + 25;
bool a[MAXN];
int n, q;
set <vector <int>> cur;
void init () {
    for (int i = 1; i <= n; i++) {
        if (!a[i]) continue;
        int j = i; while (j + 1 <= n && a[j + 1]) j++;
        cur.insert({i, j, 0});
        i = j;
    }
}
vector <vector <int>> inserted;
void add (vector <int> x, int y) {
    cur.erase(x);
    inserted.push_back({x[0], x[1], y - x[2]});
}
void insert (vector <int> x) {
    cur.insert(x);
}
int query (int l, int r, int x) { 
    int sum = 0;
    for (auto i : inserted) if (i[0] <= l && r <= i[1]) sum += i[2];
    auto z = cur.upper_bound({l, n + 1, 0});
    if (z != cur.begin()) {
        z--; auto g = *z; //cout << g[0] << " " << g[1] << '\n'; 
        if (g[0] <= l && r <= g[1]) sum += x - g[2];
    }
    return sum;
}
int main () {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        char x; cin >> x; a[i] = x == '1';
    }
    init();
    for (int t = 1; t <= q; t++) {
        string x; cin >> x;
        if (x == "query") {
            int l, r; cin >> l >> r; r--;
            cout << query(l, r, t) << '\n';
        } else {
            int x; cin >> x; a[x] ^= 1;
            if (!a[x]) {
                auto z = *(--cur.lower_bound({x + 1, 0, 0}));
                add(z, t); 
                auto l = z; l[2] = t; l[1] = x - 1;
                if (l[0] <= l[1]) insert(l);
                l = z; l[2] = t; l[0] = x + 1;
                if (l[0] <= l[1]) insert(l);
            } else {
                int mn = x, mx = x;
                if (x < n && a[x + 1]) {
                    auto z = *(cur.lower_bound({x + 1, x + 1, 0}));
                    add(z, t);
                    mx = z[1];
                }
                if (x > 1 && a[x - 1]) {
                    auto z = *(--cur.lower_bound({x, x, 0}));
                    add(z, t);
                    mn = z[0];
                }
                vector <int> z = {mn, mx, t};
                //cout << mn << " " << mx << " " << t << '\n';
                insert(z);
            }
        }   
    }
}

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