Submission #401576

#	Time	Username	Problem	Language	Result	Execution time	Memory
401576		kai824	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1195 ms	146668 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define eb emplace_back
#define mp make_pair
typedef pair<int,int> pii;
#define f first
#define s second

#ifdef local
#define debug(x,label) cerr<<"DEBUG "<<label<<" "<<x<<'\n';
#else
#define debug(x,label);
#endif

#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)

//const int mod=1000000007 or 998244353;
#define ls(x) (x&(-x))
int n,q,ft[300005];
int ans[300005],curr=0;
/*map<int,int> ft[300005];
void update(int a,int b,int upd){b++;
  //cout<<a<<' '<<b<<' '<<upd<<" UPDATE\n";
  for(;a<=n;a+=ls(a)){
    for(int x=b;x<=n;x+=ls(x)){
      if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
      else ft[a][x]+=upd;
    }
  }
}
int query(int a,int b){b++;
  int ans=0;
  for(;a;a-=ls(a)){
    for(int x=b;x;x-=ls(x)){
      //if(ft[a].find(x)==ft[a].end())continue;
      ans+=ft[a][x];
    }
  }
  return ans;
}*/ //sparse 2d fenwick TLE :(
void upddd(int p,int v){
  debug(p,"update p")
  for(;p<=n;p+=ls(p))ft[p]+=v;
}
int query(int p){
  debug(p,"query p")
  int ansss=0;
  for(;p;p-=ls(p))ansss+=ft[p];
  return ansss;
}
struct node{
  int s,e;
  vector<pair<pii,int> > v;//type,b, update value OR ans index...
  node *l,*r;
  node(int ss,int ee){
    s=ss;e=ee;
    if(s==e)l=r=NULL;
    else{
      l=new node(s,(s+e)/2);r=new node((s+e)/2+1,e);
    }
  }
  void upd(int a,int b,int c,bool upda=1){//1 to a...
    if(s==1 && e==n){
      b++;
      //if(upda)cout<<a<<' '<<b<<' '<<'\n';
    }
    if(upda==false) goto end;
    if(a<=s){
      if(upda)v.eb(mp(1,b),c);//update
      else v.eb(mp(2,b),c);//query
      return;
    }
    if(a<=(s+e)/2)l->upd(a,b,c,upda);
    r->upd(a,b,c,upda);
    return;

    end:;
    if(true){
      if(upda)v.eb(mp(1,b),c);//update
      else v.eb(mp(2,b),c);//query
    }
    if(s==e)return;
    if(a>(s+e)/2)r->upd(a,b,c,upda);
    else l->upd(a,b,c,upda);
  }
  void dfs(){
    for(auto xx:v){
      if(xx.f.f==1){
        upddd(xx.f.s,xx.s);
      }else ans[xx.s]+=query(xx.f.s);
    }
    for(auto xx:v){
      if(xx.f.f==1)upddd(xx.f.s,-xx.s);//reset ft
    }
    if(s==e)return;
    l->dfs();r->dfs();
  }
} *root;
#define update root->upd

bool lam[300005];

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int prev=0,a,b,c,d;
  cin>>n>>q;
  root=new node(1,n);
  string s;
  cin>>s;
  set<pair<pii,int> > cur;//"cur ranges"
  set<pair<pii,int> >::iterator it;
  for(int i=0;i<n;i++){
    if(s[i]=='0'){
      if(prev<=i-1){
        cur.insert(mp(mp(prev+1,i),0));
      }
      prev=i+1;
    }
    lam[i+1]=(s[i]=='1');
  }
  if(prev<=n-1){
    cur.insert(mp(mp(prev+1,n),0));
  }

  for(int i=1;i<=q;i++){
    cin>>s;
    if(s[0]=='t'){
      cin>>a;
      if(lam[a]){
        it=--cur.upper_bound(mp(mp(a,INT_MAX),-1));
        b=it->f.f;c=it->f.s;//range b to c...
        root->upd(b,n-c,i-it->s);
        cur.erase(it);
        if(b<a)cur.insert(mp(mp(b,a-1),i));
        if(a<c)cur.insert(mp(mp(a+1,c),i));
      }else{
        b=c=a;
        if(lam[a-1]){
          it=--cur.upper_bound(mp(mp(a-1,INT_MAX),-1));
          b=it->f.f;
          root->upd(it->f.f,n-it->f.s,i-it->s);
          cur.erase(it);
        }
        if(lam[a+1]){
          it=--cur.upper_bound(mp(mp(a+1,INT_MAX),-1));
          c=it->f.s;
          root->upd(it->f.f,n-it->f.s,i-it->s);
          cur.erase(it);
        }
        cur.insert(mp(mp(b,c),i));
      }
      lam[a]^=1;
    }else{
      ans[curr]=0;
      cin>>a>>b;b--;
      it=cur.upper_bound(mp(mp(a,INT_MAX),-1));
      if(it!=cur.begin()){
        it--;
        if(it->f.f<=a && b<=it->f.s){
          ans[curr]+=(i-it->s);
        }
      }
      root->upd(a,n-b,curr,0);
      //ans+=query(a,n-b);//if first index >=a, then n-first index<=n-a
      //cout<<ans<<'\n';
      curr++;
    }
  }
  //for(int i=0;i<curr;i++)cout<<ans[i]<<' ';cout<<'\n';
  debug('x',"dfsing")
  root->dfs();
  for(int i=0;i<curr;i++){
    cout<<ans[i]<<'\n';
  }
  return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message (stderr)

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:107:20: warning: unused variable 'd' [-Wunused-variable]
  107 |   int prev=0,a,b,c,d;
      |                    ^

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