Submission #161775

#	Time	Username	Problem	Language	Result	Execution time	Memory
161775		Minnakhmetov	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2703 ms	210792 KiB

street_lamps

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const int N = 3e5 + 5;

struct ST {
    vector<int> vec, t;

    void resize() {
        t.resize(vec.size() * 4);
    }

    void upd(int l, int r, int x, int v, int L, int R) {
        if (r < vec[L] || l > vec[R])
            return;
        if (l <= vec[L] && vec[R] <= r) {
            t[v] += x;
        }
        else {
            int m = (L + R) >> 1;
            upd(l, r, x, v * 2, L, m);
            upd(l, r, x, v * 2 + 1, m + 1, R);
        }
    }

    int que(int x, int v, int L, int R) {
        int ans = t[v];
        // if (L == R) {
        //     cout << "? " << x << " " << vec[L] << " : ";
        //     for (int y : vec)
        //         cout << y << " ";
        //     cout << "\n";
        // }
        if (L != R) {
            int m = (L + R) >> 1;
            if (x <= vec[m])
                ans += que(x, v * 2, L, m);
            else
                ans += que(x, v * 2 + 1, m + 1, R);
        }
        return ans;
        
    }
} t[N * 4];

struct Q {
    int type, x, y;
};

int n, q;
string s;
vector<pair<int, int>> pts;

void build(int v, int L, int R) {
    if (L == R) {
        t[v].vec = {pts[L].second};        
    }
    else {
        int m = (L + R) >> 1;
        build(v * 2, L, m);
        build(v * 2 + 1, m + 1, R);
        set_union(all(t[v * 2].vec), 
            all(t[v * 2 + 1].vec), 
            back_inserter(t[v].vec));
    }
    t[v].resize();
}

void upd(int lx, int rx, int ly, int ry, int add, int v, int L, int R) {
    if (rx < pts[L].first || lx > pts[R].first)
        return;
    if (lx <= pts[L].first && pts[R].first <= rx) {
        t[v].upd(ly, ry, add, 1, 0, t[v].vec.size() - 1);
    }
    else {
        int m = (L + R) >> 1;
        upd(lx, rx, ly, ry, add, v * 2, L, m);
        upd(lx, rx, ly, ry, add, v * 2 + 1, m + 1, R);
    }
}

int que(int x, int y, int v, int L, int R) {
    int ans = t[v].que(y, 1, 0, t[v].vec.size() - 1);
    if (L != R) {
        int m = (L + R) >> 1;
        if (make_pair(x, y) <= pts[m])
            ans += que(x, y, v * 2, L, m);
        else
            ans += que(x, y, v * 2 + 1, m + 1, R);
    }
    return ans;
}

set<pair<int, int>> st;
int curt = 0;

void insSeg(int x, int y) {
    if (x <= y) {
        st.insert({x, y});
        // cout << x << " " << y << " " << curt << "\n";
        upd(x, y, x, y, -curt, 1, 0, pts.size() - 1);
    }
}

void delSeg(int x, int y) {
    st.erase({x, y});
    // cout << x << " " << y << " " << curt << "\n";
    upd(x, y, x, y, curt, 1, 0, pts.size() - 1);
}

void toggle(int x) {
    if (s[x] == '1') {
        auto it = prev(st.lower_bound({x + 1, -1}));
        insSeg(it->first, x - 1);
        insSeg(x + 1, it->second);
        delSeg(it->first, it->second);
        s[x] = '0';
    }
    else {
        auto nt = st.lower_bound({x + 1, -1}),
            pr = (nt == st.begin() ? st.end() : prev(nt));
        int l, r;
        if (nt != st.end() && nt->first == x + 1) {
            r = nt->second;
            delSeg(nt->first, nt->second);
        }
        else {
            r = x;
        }

        if (pr != st.end() && pr->second == x - 1) {
            l = pr->first;
            delSeg(pr->first, pr->second);
        }
        else {
            l = x;
        }

        insSeg(l, r);
        s[x] = '1';
    }
}

int countAnswer(int x, int y) {
    int ans = que(x, y, 1, 0, pts.size() - 1);
    // cout << x << " " << y << " " << ans << "\n";
    auto it = st.lower_bound({x + 1, -1});
    if (it != st.begin() && prev(it)->second >= y)
        ans += curt;
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> q >> s;

    vector<Q> qr;

    for (int i = 0; i < q; i++) {
        string t;
        cin >> t;

        if (t[0] == 'q') {
            int x, y;
            cin >> x >> y;
            x--;
            y -= 2;
            qr.push_back({0, x, y});
            pts.push_back({x, y});
        }
        else {
            int x;
            cin >> x;
            x--;
            qr.push_back({1, x});
        }
    }

    sort(all(pts));
    build(1, 0, pts.size() - 1);

    for (int i = 0, j = 0; i < n; i++) {
        if (s[i] == '0') {
            j = i + 1;
        }
        else if (i == n - 1 || s[i + 1] == '0') {
            insSeg(j, i);
        }
    }


    for (Q z : qr) {
        curt++;
        if (z.type == 0) {
            cout << countAnswer(z.x, z.y) << "\n";
        }
        else {
            toggle(z.x);
        }
    }

    return 0;
}

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