Submission #1023085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023085		_8_8_	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2574 ms	360928 KiB

street_lamps

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 3e5 + 20, MOD = (int)1e9+7;


struct bit{
    vector<int> t,add;
    int n;
    void init(int s){
        n = s;
        t.assign((s + 1) * 4,0);
        add.assign((s + 1) * 4,0);
    }
    void inc(int v,int val){
        add[v] += val;
        t[v] += val;
    }
    void push(int v)
    {
        if(add[v]){
            inc(v+v,add[v]);
            inc(v+v+1,add[v]);
            add[v] = 0;
        }
    }
    void upd(int l,int r,int val,int v,int tl,int tr){
        if(l > r ||tl >r || l > tr) return;
        if(tl >= l && tr <= r){
            inc(v,val);
        }else{
            push(v);
            int tm = (tl + tr) >> 1;
            upd(l,r,val,v+v,tl,tm);
            upd(l,r,val,v+v+1,tm+1,tr);
            t[v] = t[v  + v] + t[v + v + 1];
        }
    }
    int get(int l,int r,int v,int tl,int tr){
        if(l > r || tl >r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        push(v);
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
};
vector<pair<int,int>> qr;
int n,q,a[N];
vector<int> t[N * 4],f[N];
bit b[N * 4];
void build(int v = 1,int tl = 1,int tr = n){
    if(tl == tr){
        t[v] = f[tl];
        t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
        b[v].init((int)t[v].size());
    }else{
        int tm = (tl + tr) >> 1;
        build(v+v,tl,tm);
        build(v + v + 1,tm + 1,tr);
        t[v].resize((int)t[v+v].size() + (int)t[v +v + 1].size());
        merge(t[v + v].begin(),t[v + v].end(),t[v + v + 1].begin(),t[v + v + 1].end(),t[v].begin());
        t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
        b[v].init((int)t[v].size());
    }
}
void del(set<pair<int,int>> &st,int pos){
    auto it = st.upper_bound({pos,(int)1e9});
    it--;
    auto [l,r] = *it;
    st.erase(it);
    if(l != pos){
        st.insert({l,pos-1});
    }
    if(r != pos){
        st.insert({pos+1,r});
    }
}
pair<int,int> ins(set<pair<int,int>> &st,int pos){
    if(st.empty()){
        st.insert({pos,pos});
        return {pos,pos};
    }
    auto it = st.upper_bound({pos,(int)1e9});
    if(it == st.end() || (*it).first != pos + 1){
        if(it == st.begin()){
            st.insert({pos,pos});
            return {pos,pos};
        }
        it--;
        if((*it).second + 1 != pos){
            st.insert({pos,pos});
            return {pos,pos};
        }
        int L = (*it).first;
        st.insert({L,pos});
        st.erase(it);
        return {L,pos};
    }
    int R = (*it).second;
    if(it == st.begin()){
        st.erase(it);
        st.insert({pos,R});
        return {pos,R};
    }
    it--;
    if((*it).second + 1 != pos){
        it++;
        st.erase(it);
        st.insert({pos,R});
        return {pos,R};
    }
    int L = (*it).first;
    auto it1 = it;
    it1++;
    st.erase(it1);
    st.erase(it);
    st.insert({L,R});
    return {L,R};
}
void upd(int l,int r,int l1,int r1,int val,int v = 1,int tl = 1,int tr = n){
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r){
        int it = lower_bound(t[v].begin(),t[v].end(),l1) - t[v].begin() + 1;
        int it1 = upper_bound(t[v].begin(),t[v].end(),r1) - t[v].begin();
        b[v].upd(it,it1,val,1,1,b[v].n);
    }else{
        int tm = (tl + tr) >> 1;
        upd(l,r,l1,r1,val,v+v,tl,tm);
        upd(l,r,l1,r1,val,v+v+1,tm+1,tr);
    }
}
int res = 0;
void get(int l,int r,int v = 1,int tl = 1,int tr = n){
    int it = lower_bound(t[v].begin(),t[v].end(),r) - t[v].begin();
    res += b[v].get(it + 1,it + 1,1,1,b[v].n);
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    if(l <= tm) get(l,r,v+v,tl,tm);
    else get(l,r,v+v+1,tm+1,tr);
}
int re[N];
void test(){
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        char x;
        cin >> x;
        a[i] = (x - '0');
    }
    qr.push_back({-1,-1});
    for(int i = 1;i <= q;i++)
    {
        string tp;cin >> tp;
        if(tp == "toggle"){
            int x;
            cin >> x;
            qr.push_back({x,-1});
        }else{
            int l,r;
            cin >> l >> r;
            r--;
            f[l].push_back(r);
            qr.push_back({l,r});
        }
    }
    for(int i = 1;i <= n;i++){
        sort(f[i].begin(),f[i].end());
    }
    build();
    set<pair<int,int>> o,z;
    int lst = 1;
    for(int i = 2;i <= n + 1;i++){
        if(i == n + 1 || a[i] != a[lst]){
            if(a[lst]){
                o.insert({lst,i - 1});
            }else{
                z.insert({lst,i - 1});
            }
            lst = i;
        }
    }
    for(int i = 1;i <= q;i++){
        auto [L,R] = qr[i];
        if(R == -1){
            int x = L;
            if(a[x]){
                auto it = o.upper_bound({x,1e9});
                it--;
                int l = (*it).first,r = (*it).second;
                del(o,x);
                ins(z,x);
                upd(l,x,x,r,i);
                // cout << l << ' ' << r << ' ' << x << '\n';
                // for(int j = i + 1;j <= q;j++){
                //     if(qr[j].second != -1 && qr[j].first >= l && qr[j].first <= x && qr[j].second >= x && qr[j].second <= r){
                //         re[j] += i;
                //     }
                // }
            }else{
                del(z,x);
                auto [l,r] = ins(o,x);
                upd(l,x,x,r,-i);
                // for(int j = i + 1;j <= q;j++){
                //     if(qr[j].second != -1 && qr[j].first >= l && qr[j].first <= x && qr[j].second >= x && qr[j].second <= r){
                //         // cout << i << "-\n";
                //         re[j] -= i;
                //     }
                // }   
            }
            a[x] ^= 1;
        }else{
            res = 0;
            get(L,R);
            auto it = o.upper_bound({L,1e9});
            if(it != o.begin()){
                it--;
                if((*it).second >= R){
                    res += i;
                    re[i] += i;
                }
            }   
            cout << res << '\n';
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--){
        test();
    }
}

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