Submission #520231

#	Time	Username	Problem	Language	Result	Execution time	Memory
520231		czhang2718	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2952 ms	214448 KiB

street_lamps

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
const int N=300001;

struct Fenwick{
  int n;
  vector<ll> sum;

  Fenwick(){ 
    this->n=1;
    sum.resize(1, 0);
  }

  Fenwick(int n){
    this->n=n;
    sum.resize(n+1, 0);
  }

  void add(int i, int v){
    i++;
    while(i<=n){
      sum[i]+=v;
      i+=i&-i;
    }
  }

  void add(int l, int r, int v){
    // cout << l << " to " << r << " add " << v << '\n';
    if(r<l) return;
    add(l, v); 
    add(r+1, -v);
  }

  ll get(int i){
    i++;
    ll ret=0;
    while(i){
      ret+=sum[i];
      i-=i&-i;
    }
    return ret;
  }
};

int n, q;
vi range[4*N];
Fenwick seg[4*N];
vector<int> li[N];
int r[N], l[N];
string init;

void build(int x, int lx, int rx){
  if(rx-lx==1){
    for(int i:li[lx]){
      range[x].push_back(i);
    }
    sort(all(range[x]), [&](int i, int j){ return make_pair(r[i], i)<make_pair(r[j], j); });
    Fenwick bit(sz(range[x]));
    seg[x]=bit;
    return;
  }
  int m=(lx+rx)/2;
  build(2*x+1, lx, m);
  build(2*x+2, m, rx);

  int n=sz(range[2*x+1]); m=sz(range[2*x+2]);
  int i=0, j=0;
  while(i+j<n+m){
    if(i==n){
      range[x].push_back(range[2*x+2][j]);
      j++;
    }
    else if(j==m){
      range[x].push_back(range[2*x+1][i]);
      i++;
    }
    else{
      if(make_pair(r[range[2*x+1][i]], range[2*x+1][i])<make_pair(r[range[2*x+2][j]], range[2*x+2][j])){
        range[x].push_back(range[2*x+1][i]);
        i++;
      }
      else{
        range[x].push_back(range[2*x+2][j]);
        j++;
      }
    }
  }
  Fenwick bit(n+m);
  seg[x]=bit;
}

void upd(int L, int M, int R, int v, int x, int lx, int rx){
  if(lx>M || rx<=L) return;
  if(lx>=L && rx<=M+1){
    int n=sz(range[x]);
    if(!n) return;
    int a=n-1;
    for(int i=n-1; i; i/=2){
      while(a-i>=0 && r[range[x][a-i]]>=M) a-=i;
    }
    int b=0;
    for(int i=n-1; i; i/=2){
      while(b+i<n && r[range[x][b+i]]<=R) b+=i;
    }
    if(r[range[x][a]]>=M && r[range[x][a]]<=R) seg[x].add(a, b, v);
    return;
  }
  int m=(lx+rx)/2;
  upd(L, M, R, v, 2*x+1, lx, m);
  upd(L, M, R, v, 2*x+2, m, rx);
}

void upd(int L, int M, int R, int v){
  upd(L, M, R, v, 0, 0, n);
}

ll query(int i, int x, int lx, int rx){
  int j=0;
  for(int add=sz(range[x])-1; add; add/=2){
    while(j+add<sz(range[x]) && make_pair(r[range[x][j+add]], range[x][j+add])<=make_pair(r[i], i)) j+=add;
  }
  assert(range[x][j]==i);
  ll ret=seg[x].get(j);
  if(rx-lx==1) return ret;
  int m=(lx+rx)/2;
  if(l[i]<m) ret+=query(i, 2*x+1, lx, m);
  else ret+=query(i, 2*x+2, m, rx);
  return ret;
}

ll query(int i){
  return query(i, 0, 0, n);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> q >> init;
  vector<pii> qu;
  for(int i=1; i<=q; i++){
    string op; cin >> op;
    if(op=="toggle"){
      int j; cin >> j;
      --j;
      qu.push_back({0, j});
    }
    else{
      cin >> l[i] >> r[i];
      --l[i]; r[i]-=2;
      qu.push_back({1, i});
      li[l[i]].push_back(i);
    }
  }
  build(0, 0, n);
  set<pii> s={{-1e9,-1e9},{1e9,1e9}};

  auto on=[&](int i, int X){ // turn ith lamp on, update s, segtree
    auto it=s.lower_bound({i, 0});
    auto prv=prev(it);
    int l=((*prv).s==i-1?(*prv).f:i);
    int r=((*it).f==i+1?(*it).s:i);
    if(s.find({l, i-1})!=s.end()) s.erase({l, i-1});
    if(s.find({i+1, r})!=s.end()) s.erase({i+1, r});
    s.insert({l, r});
    // cout << "on " << l << " " << i << " " << r << " " << X << '\n';
    upd(l, i, r, X);
  };

  auto off=[&](int i, int X){
    auto it=--s.upper_bound({i, 1e9});
    int l=(*it).f;
    int r=(*it).s;
    upd(l, i, r, X);
    s.erase({l, r});
    if(l!=i) s.insert({l, i-1});
    if(r!=i) s.insert({i+1, r});
  };

  Fenwick state(n);
  for(int i=0; i<n; i++){
    if(init[i]=='1') state.add(i, 1), on(i, 0);
  }
  for(int t=1; t<=q; t++) {
    auto p=qu[t-1];
    int op=p.f;
    int i=p.s;
    if(op){
      assert(i==t);
      cout << query(i)+(state.get(r[i])-state.get(l[i]-1)==r[i]-l[i]+1?t:0) << "\n";
    }
    else{
      if(state.get(i)-state.get(i-1)) off(i, t), state.add(i, -1);
      else on(i, -t), state.add(i, 1);
    }
  }
}


// set of all-1 range
// 2d segtree, sort l, sort r
// need ind[x] in each segtree layer

// toggle->1: [a, b, c] for l[a,b], r[b,c] -t
// toggle->0: [a, b, c] for l[a,b], r[b,c] +t
// query: sum of segtree vals at each layer

// inner- range add, get point OR fenwick ?
// outer: ind[i][x], vector for lowerbound

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