Submission #477634

#	Time	Username	Problem	Language	Result	Execution time	Memory
477634		RGBB	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2795 ms	120200 KiB

street_lamps

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pi;
const int MAX=3*1e5;
//input
int n,q,state[MAX],inp[MAX][2];
bool type[MAX];//true is toggle, false is query
string s;
//first sweep
int beg[MAX];
map<int,int>lines;
vector<pi>add[MAX],sub[MAX];//location, value
void firstSweep(){
    int orig=0;
    for(int i=0;i<n;i++){
        if(state[i]==1){
            if(i!=0&&state[i-1]==1)lines[orig]++;
            else{
                lines[i]=i;
                orig=i;
            }
        }
        else beg[i]=i-1;
    }
    for(auto&[i,j]:lines)for(int k=i;k<=j;k++)beg[k]=j;
    for(int i=0;i<q-1;i++){
        if(!type[i])continue;
        int cur=inp[i][0];
        if(state[cur]==1){
            state[cur]=0;
            pi cl=*prev(lines.upper_bound(cur));
            lines.erase(lines.find(cl.first));
            if(cur!=cl.first)lines[cl.first]=cur-1;
            if(cur!=cl.second)lines[cur+1]=cl.second;
            add[cl.first].push_back({i+1,cur-1});
            sub[cur].push_back({i+1,cur-1});
        }
        else{
            state[cur]=1;
            int lef=cur;
            int rig=cur;
            if(lines.find(cur+1)!=lines.end()){
                rig=lines[cur+1];
                lines.erase(lines.find(cur+1));
            }
            if(lines.upper_bound(cur)!=lines.begin()){
                pi cl=*prev(lines.upper_bound(cur));
                if(cl.second==cur-1){
                    lef=cl.first;
                    lines.erase(lines.find(cl.first));
                }
            }
            lines[lef]=rig;
            add[lef].push_back({i+1,rig});
            sub[cur].push_back({i+1,rig});
        }
    }
}
//second sweep
struct sparseBIT{
    vector<pi>todo;
    int cnt[MAX+1],st[MAX+1];
    vector<int>val,bit;
    void init(){
        int lst[MAX+1];
        for(int i=0;i<=MAX;i++)lst[i]=cnt[i]=0;
        sort(todo.begin(),todo.end(),[](const pi&a,const pi&b){return a.second<b.second;});
        for(pi t:todo){
            for(int x=t.first;x<=MAX;x+=x&-x){
                if(lst[x]!=t.second){
                    lst[x]=t.second;
                    cnt[x]++;
                }
            }
        }
        int sum=0;
        for(int i=0;i<=MAX;i++){
            lst[i]=0;
            st[i]=sum;
            sum+=cnt[i];
        }
        val.resize(sum);
        bit.resize(sum);
        for(pi t:todo){
            for(int x=t.first;x<=MAX;x+=x&-x){
                if(lst[x]!=t.second){
                    lst[x]=t.second;
                    val[st[x]++]=t.second;
                }
            }
        }
    }
    void push(int x,int y){
        if(x<0||x>=MAX||y<0||y>=MAX)return;
        todo.push_back({x+1,y+1});
    }
    int rank(int y,int l,int r){return upper_bound(begin(val)+l,begin(val)+r,y)-begin(val)-l;}
    void UPDATE(int x,int y,int t){
        int z=st[x]-cnt[x];
        for(y=rank(y,z,st[x]);y<=cnt[x];y+=y&-y)bit[z+y-1]+=t;
    }
    void update(int x,int y,int t){
        if(x<0||x>=MAX||y<0||y>=MAX)return;
        x++;
        y++;
        for(;x<=MAX;x+=x&-x)UPDATE(x,y,t);
    }
    int QUERY(int x,int y){
        int ret=0;
        int z=st[x]-cnt[x];
        for(y=rank(y,z,st[x]);y;y-=y&-y)ret+=bit[z+y-1];
        return ret;
    }
    int query(int x,int y){
        if(x<0||x>=MAX||y<0||y>=MAX)return 0;
        x++;
        y++;
        int ret=0;
        for(;x;x-=x&-x)ret+=QUERY(x,y);
        return ret;
    }
};
int val[MAX],outp[MAX];
vector<pi>query[MAX];
set<int>nei;
sparseBIT bit;
void processInsert(int p,int v){
    nei.insert(p);
    val[p]=v;
    int nxt=*next(nei.find(p));
    bit.update(p,MAX-1-v,nxt-p);
    if(p!=0){
        int prv=*prev(nei.find(p));
        bit.update(prv,MAX-1-val[prv],p-nxt);
    }
}
void processDelete(int p,int v){
    int nxt=*next(nei.find(p));
    bit.update(p,MAX-1-v,p-nxt);
    if(p!=0){
        int prv=*prev(nei.find(p));
        bit.update(prv,MAX-1-val[prv],nxt-p);
    }
    nei.erase(nei.find(p));
}
int processQuery(int p,int v){
    int prv=*prev(nei.upper_bound(p));
    int ret=bit.query(prv-1,MAX-1-v);
    if(val[prv]>=v)ret+=p-prv+1;
    return ret;
}
void secondSweep(){
    nei.insert(q);
    for(int i=0;i<n;i++)bit.push(0,MAX-1-beg[i]);
    for(int i=0;i<n;i++)for(pi j:add[i])bit.push(j.first,MAX-1-j.second);
    bit.init();
    for(int i=0;i<n;i++){
        processInsert(0,beg[i]);
        for(pi j:add[i])processInsert(j.first,j.second);
        for(pi j:query[i])outp[j.first]=processQuery(j.first,j.second);
        for(pi j:sub[i])processDelete(j.first,j.second);
        processDelete(0,beg[i]);
    }
}
//driver
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>q>>s;
    for(int i=0;i<n;i++)state[i]=s[i]-'0';
    for(int i=0;i<q;i++){
        string op;
        cin>>op;
        if(op=="toggle"){
            type[i]=true;
            cin>>inp[i][0];
            inp[i][0]--;
        }
        else{
            type[i]=false;
            cin>>inp[i][0]>>inp[i][1];
            inp[i][0]--;
            inp[i][1]-=2;
        }
    }
    firstSweep();
    for(int i=0;i<q;i++)if(!type[i])query[inp[i][0]].push_back({i,inp[i][1]});
    secondSweep();
    for(int i=0;i<q;i++)if(!type[i])cout<<outp[i]<<"\n";
}

Compilation message (stderr)

street_lamps.cpp: In function 'void firstSweep()':
street_lamps.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto&[i,j]:lines)for(int k=i;k<=j;k++)beg[k]=j;
      |              ^

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