Submission #865965

#	Time	Username	Problem	Language	Result	Execution time	Memory
865965		jk410	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	559 ms	44260 KiB

street_lamps

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define all(v) v.begin(),v.end()
using namespace std;
struct interval{
    int l,r,t;
    bool operator<(const interval &tmp)const{
        if (l!=tmp.l)
            return l<tmp.l;
        return r<tmp.r;
    }
};
struct query{
    int t,mode,x,y;
};
int N,Q;
string S;
set<interval> Set;
vector<query> Queries[300001];
int Ans[300001];
int Tree[300001];
void fenwickUpdate(int x,int val){
    while (x<=N){
        Tree[x]+=val;
        x+=x&-x;
    }
}
int fenwickQuery(int x){
    int ret=0;
    while (x){
        ret+=Tree[x];
        x-=x&-x;
    }
    return ret;
}
void solve(int l,int r){
    if (l==r)
        return;
    int m=(l+r)>>1;
    solve(l,m);
    solve(m+1,r);
    vector<query> qv;
    for (int i=l; i<=m; i++){
        for (query j:Queries[i]){
            if (!j.mode)
                qv.push_back(j);
        }
    }
    for (int i=m+1; i<=r; i++){
        for (query j:Queries[i]){
            if (j.mode)
                qv.push_back(j);
        }
    }
    stable_sort(all(qv),[&](query a,query b)->bool{
        return a.t<b.t;
    });
    for (query i:qv){
        if (i.mode)
            Ans[i.x]+=fenwickQuery(i.y)*i.mode;
        else
            fenwickUpdate(i.x,i.y);
    }
    for (query i:qv){
        if (!i.mode)
            fenwickUpdate(i.x,-i.y);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>Q>>S;
    for (int i=1,j=0; i<=N; i++){
        if (S[i-1]=='1'){
            if (!j)
                j=i;
            if (i==N||S[i]=='0'){
                Set.insert({j,i,0});
                j=0;
            }
        }
    }
    fill(Ans+1,Ans+Q+1,-1);
    for (int t=1; t<=Q; t++){
        string s;
        cin>>s;
        if (s[0]=='t'){
            int x;
            cin>>x;
            auto it=Set.lower_bound({x+1,x+1,0});
            if (it!=Set.begin()&&prev(it)->r>=x){//x가 켜져 있음
                interval cur=*(--it);
                Queries[t].push_back({cur.r,0,cur.l,t-cur.t});
                Set.erase(it);
                if (cur.l<x)
                    Set.insert({cur.l,x-1,t});
                if (x<cur.r)
                    Set.insert({x+1,cur.r,t});
            }
            else{//x가 꺼져 있음
                interval cur={x,x,t};
                if (it!=Set.begin()&&prev(it)->r==x-1){
                    cur.l=(--it)->l;
                    Queries[t].push_back({it->r,0,it->l,t-it->t});
                    it=Set.erase(it);
                }
                if (it!=Set.end()&&it->l==x+1){
                    cur.r=it->r;
                    Queries[t].push_back({it->r,0,it->l,t-it->t});
                    Set.erase(it);
                }
                Set.insert(cur);
            }
        }
        else{
            Ans[t]=0;
            int l,r;
            cin>>l>>r;
            r--;
            auto it=Set.lower_bound({l+1,l+1,0});
            if (it!=Set.begin()&&prev(it)->r>=r)
                Ans[t]+=t-prev(it)->t;
            Queries[t].push_back({r-1,-1,t,l});
            Queries[t].push_back({N,1,t,l});
        }
    }
    solve(1,Q);
    for (int i=1; i<=Q; i++){
        if (Ans[i]!=-1)
            cout<<Ans[i]<<"\n";
    }
    return 0;
}

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