Submission #1038086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038086		vladilius	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	793 ms	248044 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int inf = numeric_limits<int> :: max();
 
struct FT{
    vector<int> bit;
    int n;
    void init(int ns){
        n = ns;
        bit.resize(n + 1);
    }
    int get(int v){
        int out = 0;
        while (v > 0){
            out += bit[v];
            v = (v & (v + 1)) - 1;
        }
        return out;
    }
    void upd(int v, int k){
        while (v <= n){
            bit[v] += k;
            v |= (v + 1);
        }
    }
    void updr(int l, int r, int k){
        if (l > r) return;
        upd(l, k);
        upd(r + 1, -k);
    }
};
 
struct ST{
    struct node{
        vector<int> x;
        int lg;
        FT T;
    };
    vector<node> t;
    vector<vector<int>> mp;
    int n, q;
    ST(int ns, int qs){
        n = ns; q = qs;
        t.resize(4 * n);
        for (int i = 1; i < t.size(); i++){
            t[i].x.pb(0);
        }
        mp.resize(q + 1);
        int lg = log2(n) + 5;
        for (int i = 1; i <= q; i++){
            mp[i].resize(lg + 1);
        }
        bld(1, 1, n, 0);
    }
    void bld(int v, int tl, int tr, int k){
        t[v].lg = k++;
        if (tl == tr) return;
        int tm = (tl + tr) / 2, vv = 2 * v;
        bld(vv, tl, tm, k);
        bld(vv + 1, tm + 1, tr, k);
    }
    vector<int> :: iterator it1, it2;
    void upd(int v, int tl, int tr, int& l, int& r, int& lr, int& rr, int& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            it1 = lower_bound(t[v].x.begin(), t[v].x.end(), lr);
            it2 = upper_bound(t[v].x.begin(), t[v].x.end(), rr);
            if (it1 == it2) return;
            it2--;
            int l1 = (int) (it1 - t[v].x.begin()), r1 = (int) (it2 - t[v].x.begin());
            t[v].T.updr(max(1, l1), r1, x);
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        upd(vv, tl, tm, l, r, lr, rr, x);
        upd(vv + 1, tm + 1, tr, l, r, lr, rr, x);
    }
    void upd(int l1, int r1, int l2, int r2, int x){
        upd(1, 1, n, l1, r1, l2, r2, x);
        // cout<<x<<" -> "<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
    }
    int get(int v, int tl, int tr, int& l, int& i){
        int out = t[v].T.get(mp[i][t[v].lg]);
        if (tl == tr){
            return out;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (l <= tm){
            return out + get(vv, tl, tm, l, i);
        }
        return out + get(vv + 1, tm + 1, tr, l, i);
    }
    int get(int l, int i){
        return get(1, 1, n, l, i);
    }
    void add(int v, int tl, int tr, int& l, int& r, int& i){
        t[v].x.pb(r);
        mp[i][t[v].lg] = (int) t[v].x.size() - 1;
        if (tl == tr) return;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (l <= tm){
            add(vv, tl, tm, l, r, i);
        }
        else {
            add(vv + 1, tm + 1, tr, l, r, i);
        }
    }
    void add(int l, int r, int i){
        add(1, 1, n, l, r, i);
    }
    void build(){
        for (int i = 1; i < t.size(); i++){
            t[i].T.init((int) t[i].x.size() - 1);
        }
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q; cin>>n>>q;
    string s; cin>>s; s = '#' + s;
    vector<pii> qs = {{}};
    vector<int> rr;
    for (int qq = 1; qq <= q; qq++){
        string type; cin>>type;
        if (type == "toggle"){
            int k; cin>>k;
            qs.pb({k, 0});
        }
        else {
            int l, r; cin>>l>>r;
            qs.pb({l, --r});
            rr.pb(qq);
        }
    }
    
    auto cmp = [&](int i, int j){
        if (qs[i].ss == qs[j].ss){
            return qs[i].ff < qs[j].ff;
        }
        return qs[i].ss < qs[j].ss;
    };
    sort(rr.begin(), rr.end(), cmp);
    
    ST T(n, q);
    for (int i: rr){
        T.add(qs[i].ff, qs[i].ss, i);
    }
    T.build();
    
    set<pii> st;
    int i = 1;
    while (i <= n){
        if (s[i] == '0'){
            i++;
            continue;
        }
        int j = i;
        while (j <= n && s[j] == '1'){
            j++;
        }
        st.ins({i, j - 1});
        i = j;
    }
 
    for (int i = 1; i <= q; i++){
        auto& [a, b] = qs[i];
        if (!b){
            if (s[a] == '0'){
                st.ins({a, a});
                auto it = st.find({a, a});
                vector<pii> add;
                if (it != st.begin()){
                    auto it1 = prev(it);
                    auto [l, r] = *it1;
                    if (r == (a - 1)){
                        add.pb({l, r});
                    }
                }
                if (it != prev(st.end())){
                    auto it1 = next(it);
                    auto [l, r] = *it1;
                    if (l == (a + 1)){
                        add.pb({l, r});
                    }
                }
                if (add.size() == 2){
                    st.erase(it);
                    for (auto p: add) st.erase(p);
                    pii R = {add[0].ff, add[1].ss};
                    T.upd(R.ff, a, a, R.ss, -i);
                    st.ins(R);
                }
                else if (add.size() == 1){
                    st.erase(it);
                    for (auto p: add) st.erase(p);
                    pii R = ((add[0].ff > a) ? make_pair(a, add[0].ss) : make_pair(add[0].ff, a));
                    T.upd(R.ff, a, a, R.ss, -i);
                    st.ins(R);
                }
                else {
                    T.upd(a, a, a, a, -i);
                }
                s[a] = '1';
            }
            else {
                auto it = st.lower_bound({a + 1, -inf}); it--;
                auto [l, r] = *it;
                T.upd(l, a, a, r, i);
                st.erase(it);
                if (l < a) st.ins({l, a - 1});
                if (a < r) st.ins({a + 1, r});
                s[a] = '0';
            }
        }
        else {
            int out = T.get(qs[i].ff, i);
            if (!st.empty()){
                auto it = st.lower_bound({a + 1, -inf});
                if (it != st.begin()){
                    it--;
                    if ((*it).ff <= a && b <= (*it).ss){
                        out += i;
                    }
                }
            }
            cout<<out<<"\n";
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'ST::ST(int, int)':
street_lamps.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 1; i < t.size(); i++){
      |                         ~~^~~~~~~~~~
street_lamps.cpp: In member function 'void ST::build()':
street_lamps.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int i = 1; i < t.size(); i++){
      |                         ~~^~~~~~~~~~

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