Submission #520220

#	Time	Username	Problem	Language	Result	Execution time	Memory
520220		czhang2718	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5100 ms	524288 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 rc[4*N], range[4*N];
Fenwick seg[4*N];
vector<int> li[N];
int r[N], l[N];
string init;
map<pii, int> ind;

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 r[i]<r[j]; });
    for(int i:range[x]){
      rc[x].push_back(r[i]);
    }
    for(int i=0; i<sz(range[x]); i++){
      ind[{range[x][i], x}]=i;
    }
    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(rc[2*x+1][i]<rc[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++;
      }
    }
  }
  // cout << lx << " " << rx << " range: ";
  for(int i=0; i<sz(range[x]); i++){
    ind[{range[x][i], x}]=i;
    // cout << range[x][i] << " ";
    rc[x].push_back(r[range[x][i]]);
  }
  // cout << '\n';
  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 a=lower_bound(all(rc[x]), M)-rc[x].begin();
    int b=upper_bound(all(rc[x]), R)-rc[x].begin()-1;
    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){
  ll ret=seg[x].get(ind[{i, x}]);
  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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20