Submission #126444

#	Time	Username	Problem	Language	Result	Execution time	Memory
126444		keko37	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2634 ms	117484 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 300005;
const int SIZ = 120;

int n, q, ofs = 1, cnt;
string s;
map <int, int> mp, rst;
set <int> st;
set <int> :: iterator it;
int t[MAXN * SIZ], lef[MAXN * SIZ], rig[MAXN * SIZ];

struct tournament {
    int root;
    tournament () {
        root = ++cnt;
    }
    void update (int x, int pos, int lo, int hi, int val) {
        if (lo == hi) {
            t[x] += val;
            return;
        }
        int mid = (lo + hi) / 2;
        if (pos <= mid) {
            if (lef[x] == 0) lef[x] = ++cnt;
            update(lef[x], pos, lo, mid, val);
        } else {
            if (rig[x] == 0) rig[x] = ++cnt;
            update(rig[x], pos, mid+1, hi, val);
        }
        t[x] = t[lef[x]] + t[rig[x]];
    }
    int upit (int x, int from, int to, int lo, int hi) {
        if (x == 0) return 0;
        if (from <= lo && hi <= to) return t[x];
        if (to < lo || hi < from) return 0;
        return upit(lef[x], from, to, lo, (lo + hi)/2) + upit(rig[x], from, to, (lo + hi)/2+1, hi);
    }
} fen[MAXN];

void ubaci (int x, int y, int val) {
    for (; x < MAXN; x += x&-x) {
        fen[x].update(fen[x].root, y, 0, ofs-1, val);
    }
}

int upit (int x, int y) {
    int res = 0;
    for (; x > 0; x -= x&-x) {
        res += fen[x].upit(fen[x].root, y, ofs-1, 0, ofs-1);
    }
    return res;
}

void dodaj (int a, int b, int t) {
    st.insert(a);
    mp[a] = t;
    rst[a] = b;
}

void brisi (int a, int b, int t) {
    ubaci(a, b, t - mp[a]);
    st.erase(a);
    mp.erase(a);
    rst.erase(a);
}

void precompute () {
    int lim = -1;
    for (int i=1; i<=n; i++) {
        if (s[i] == '1' && (i == 1 || s[i-1] == '0')) lim = i;
        if (s[i] == '1' && (i == n || s[i+1] == '0')) {
            dodaj(lim, i, 0);
        }
    }
}

void ispis () {
    cout << "ispis" << endl;
    for (auto x : st) {
        cout << "bla " << x << " " << rig[x] << "  " << mp[x] << endl;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> s;
    s = '.' + s;
    while (ofs < n+1) ofs *= 2;
    precompute();
    for (int i=1; i<=q; i++) {
        string t;
        cin >> t;
        if (t == "query") {
            int a, b;
            cin >> a >> b; b--;
            int res = upit(a, b);
            it = st.upper_bound(a);
            if (it != st.begin()) {
                it--;
                if (b <= rst[*it]) {
                    res += i - mp[*it];
                }
            }
            cout << res << '\n';
        } else {
            int x;
            cin >> x;
            if (s[x] == '0') {
                s[x] = '1';
                int ll = x, rr = x;
                it = st.upper_bound(x);
                if (it != st.end() && *it == x+1) {
                    rr = rst[*it];
                    brisi(*it, rst[*it], i);
                }
                it = st.upper_bound(x);
                if (it != st.begin()) {
                    it--;
                    if (rst[*it] == x-1) {
                        ll = *it;
                        brisi(*it, rst[*it], i);
                    }
                }
                dodaj(ll, rr, i);
            } else {
                s[x] = '0';
                it = st.upper_bound(x); it--;
                int ll = *it;
                int rr = rst[*it];
                brisi(ll, rr, i);
                if (ll <= x-1) dodaj(ll, x-1, i);
                if (x+1 <= rr) dodaj(x+1, rr, i);
            }
        }
    }
    return 0;
}

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