Submission #1326557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326557		ee23b179_cp	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	2342 ms	73096 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Node {
    int l = 0, r = 0;
    pair<ll,int> val = {0,0};
};

const int MAXNODE = 2'000'000;
vector<Node> seg(MAXNODE);
int nxt = 1;

int N;

void update(int &cur, int xl, int xr, int pos, ll add, int cnt){
    if(!cur) cur = nxt++;
    seg[cur].val.first += add;
    seg[cur].val.second += cnt;
    if(xl == xr) return;
    int xm = (xl + xr) >> 1;
    if(pos <= xm) update(seg[cur].l, xl, xm, pos, add, cnt);
    else update(seg[cur].r, xm+1, xr, pos, add, cnt);
}

pair<ll,int> query(int cur, int xl, int xr, int l, int r){
    if(!cur || l > r) return {0,0};
    if(l == xl && r == xr) return seg[cur].val;
    int xm = (xl + xr) >> 1;
    pair<ll,int> ans = {0,0};
    if(l <= xm){
        auto t = query(seg[cur].l, xl, xm, l, min(r,xm));
        ans.first += t.first; ans.second += t.second;
    }
    if(r > xm){
        auto t = query(seg[cur].r, xm+1, xr, max(l,xm+1), r);
        ans.first += t.first; ans.second += t.second;
    }
    return ans;
}

vector<array<int,5>> ev;
vector<ll> onSum, offSum;
vector<int> onCnt, offCnt;
int rootOn = 0, rootOff = 0;

void cdq(int l, int r){
    if(l == r) return;
    int m = (l+r)>>1;
    cdq(l,m); cdq(m+1,r);

    sort(ev.begin()+l, ev.begin()+m+1,
         [](auto &A, auto &B){ return A[1] < B[1]; });
    sort(ev.begin()+m+1, ev.begin()+r+1,
         [](auto &A, auto &B){ return A[1] < B[1]; });

    int i=l, j=m+1;
    stack<tuple<int,ll,int>> stk;

    while(i<=m || j<=r){
        if(j>r || (i<=m && ev[i][1] < ev[j][1])){
            auto &e = ev[i++];
            if(e[3]==1){
                update(rootOn,0,N-1,e[2],e[0],1);
                stk.push({e[2],e[0],1});
            }
            else if(e[3]==-1){
                update(rootOff,0,N-1,e[2],e[0],1);
                stk.push({e[2],e[0],-1});
            }
        } else {
            auto &e = ev[j++];
            if(e[3]==0){
                int id = e[4];
                auto on = query(rootOn,0,N-1,e[2]+1,N-1);
                auto off = query(rootOff,0,N-1,e[2]+1,N-1);
                onSum[id]+=on.first; onCnt[id]+=on.second;
                offSum[id]+=off.first; offCnt[id]+=off.second;
            }
        }
    }

    while(!stk.empty()){
        auto [pos,t,tp] = stk.top(); stk.pop();
        if(tp==1) update(rootOn,0,N-1,pos,-t,-1);
        else update(rootOff,0,N-1,pos,-t,-1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> N >> q;
    string s; cin >> s;

    set<pair<int,int>> segs;

    for(int i=0;i<N;i++){
        if(s[i]=='1'){
            int l=i;
            while(i+1<N && s[i+1]=='1') i++;
            segs.insert({l,i});
            ev.push_back({0,l,i,1});
        }
    }

    int qc=0;
    vector<int> qtime;

    for(int t=1;t<=q;t++){
        string type; cin >> type;
        if(type=="toggle"){
            int x; cin >> x; x--;

            if(s[x]=='0'){
                int L=x,R=x;
                auto it=segs.lower_bound({x,x});
                if(it!=segs.end() && it->first==x+1){
                    R=it->second;
                    ev.push_back({t,x+1,R,-1});
                    segs.erase(it);
                }
                it=segs.lower_bound({x,x});
                if(it!=segs.begin()){
                    --it;
                    if(it->second==x-1){
                        L=it->first;
                        ev.push_back({t,L,x-1,-1});
                        segs.erase(it);
                    }
                }
                segs.insert({L,R});
                ev.push_back({t,L,R,1});
                s[x]='1';
            } else {
                auto it=prev(segs.upper_bound({x,x}));
                int L=it->first,R=it->second;
                segs.erase(it);
                ev.push_back({t,L,R,-1});
                if(L<x){
                    segs.insert({L,x-1});
                    ev.push_back({t,L,x-1,1});
                }
                if(R>x){
                    segs.insert({x+1,R});
                    ev.push_back({t,x+1,R,1});
                }
                s[x]='0';
            }
        } else {
            int a,b; cin >> a >> b;
            ev.push_back({t,a,b-3,0,qc++});
            qtime.push_back(t);
        }
    }

    sort(ev.begin(), ev.end());

    onSum.assign(qc,0);
    offSum.assign(qc,0);
    onCnt.assign(qc,0);
    offCnt.assign(qc,0);

    cdq(0,(int)ev.size()-1);

    for(int i=0;i<qc;i++){
        ll ans = offSum[i]-onSum[i];
        if(onCnt[i]>offCnt[i]) ans+=qtime[i];
        cout<<ans<<"\n";
    }
}

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