Submission #1022521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022521		_8_8_	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5036 ms	162872 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;
    int n;
    void init(int s){
        n = s;
        t.assign(s + 1,0);
    }
    void upd(int pos,int val,int n){
        while(pos <= n){
            t[pos] += val;
            pos += pos & -pos;
        }
    }
    int get(int i){
        int ret = 0;
        while(i >= 1){
            ret += t[i];
            i -= i & -i;
        }
        return ret;
    }
    int get(int l,int r){
        return get(r) - get(l - 1);
    }
};
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({(*it).first,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){
        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 x,int v = 1,int tl = 1,int tr = n){
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r){
        int val = r;
        if(t[v].empty() || t[v][0] > val) return;
        int it = upper_bound(t[v].begin(),t[v].end(),val) - t[v].begin();it--;
        b[v].upd(it + 1,x,(int)b[v].n);
    }else{
        int tm = (tl + tr) >> 1;
        upd(l,r,x,v+v,tl,tm);
        upd(l,r,x,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,b[v].n);
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    get(l,r,v+v,tl,tm);
    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);
                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);
                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;
                    }
                }   
            }
            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){
                    re[i] += i;
                }
            }
            cout << re[i] << '\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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20