Submission #1191522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191522		epicci23	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1848 ms	252320 KiB

street_lamps

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 3e5 + 5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<array<int,2>> v;
int fw[N], tot;
vector<array<int,3>> Ops;

void add(int c,int u){
  for(;c<N;c+=c&-c) fw[c] += u;
}

int get_prefix(int c,int res = 0){
  for(;c;c-=c&-c) res += fw[c];
  return res;
}

vector<int> T[4 * N], F[4 * N];

void Upd(int rt,int ind,int val){
  for(;ind < sz(F[rt]); ind += ind & -ind) F[rt][ind] += val;
}

int Get(int rt,int ind,int res = 0){
  for(;ind;ind-=ind&-ind) res += F[rt][ind];
  return res;
}

void Add_Node(int rt,int l,int r,int id){
  T[rt].push_back(id);
  F[rt].push_back(0);
  if(l == r) return;
  int mid = (l + r) / 2;
  if(v[id][1] <= mid) Add_Node(rt * 2, l, mid, id);
  else Add_Node(rt * 2 + 1, mid + 1, r, id);
}

void Query(int rt,int l,int r,int id){
  int it = lower_bound(all(T[rt]), id) - T[rt].begin();
  if(it < sz(T[rt]) && T[rt][it] == id) tot += Get(rt, it + 1);
  if(l == r) return;
  int mid = (l + r) / 2;
  if(v[id][1] <= mid) Query(rt * 2, l, mid, id);
  else Query(rt * 2 + 1, mid + 1, r, id);
}


void upd(int rt,int l,int r,int gl,int gr,int pl,int pr,int val){
  if(r < gl || l > gr) return;
  if(l >= gl && r <= gr){
    if(T[rt].empty() || v[T[rt].back()][0] < pl || v[T[rt][0]][0] > pr) return;
    int l = 0, r = sz(T[rt]) - 1;
    while(l < r){
      int mid = (l + r) / 2;
      if(v[T[rt][mid]][0] < pl) l = mid + 1;
      else r = mid;
    }
    int hml = l;

    l = 0, r = sz(T[rt]) - 1;
    while(l < r){
      int mid = (l + r + 1) / 2;
      if(v[T[rt][mid]][0] > pr) r = mid - 1;
      else l = mid;
    }

    int hmr = l;

    if(hml > hmr) return;

    Upd(rt, hml + 1, val);
    Upd(rt, hmr + 2, -val);
    return;
  }
  int mid = (l + r) / 2;
  upd(rt * 2, l, mid, gl, gr, pl, pr, val), upd(rt * 2 + 1, mid + 1, r, gl, gr, pl, pr, val);
}

void _(){
	int n,q;
  cin >> n >> q;
  
  for(int i = 0; i < 4 * N; i++){
    F[i].push_back(0);
    F[i].push_back(0);
  }

  set<int> s0;
   
  string s; cin >> s;
  s = " " + s;
 
  for(int i = 1; i <= n; i++) add(i, s[i] - '0');
  
  s0.insert(0), s0.insert(n + 1);

  for(int i = 1; i <= n; i++) if(s[i] == '0') s0.insert(i);
  
  for(int i = 0; i < q; i++){
    string op; cin >> op;
    if(op == "query"){
      int l, r;
      cin >> l >> r;
      r--;
      v.push_back({r, l});
      Ops.push_back({0, l, r});
    }
    else{
      int ind; cin >> ind;
      Ops.push_back({1, ind, ind});
    }
  }

  sort(all(v));
  v.erase(unique(all(v)), v.end());
  int m = sz(v);

  for(int i = 0; i < m; i++) Add_Node(1,1,n,i);
  
  for(int i = 1; i <= q; i++){
    if(Ops[i - 1][0] == 0){
      tot = 0;
      //cout << " l: " << Ops[i][1] << ' ' << " r : " << Ops[i][2] << '\n'; 
      int hm = lower_bound(all(v), array<int,2>{Ops[i - 1][2], Ops[i - 1][1]}) - v.begin();
      Query(1, 1, n, hm);
      if(get_prefix(Ops[i - 1][2]) - get_prefix(Ops[i - 1][1] - 1) == Ops[i - 1][2] - Ops[i - 1][1] + 1) tot += i; // maybe i + 1?
      cout << tot << '\n';
    }
    else{
      int ind = Ops[i - 1][1];
      if(s[ind] == '1'){
        int r = *s0.lower_bound(ind);
        int l = *(--s0.lower_bound(ind));
        
        //cout << " gl: " << l << ' ' << " gr : " << r << '\n';

        upd(1,1,n,l+1,ind,ind,r-1,i);

        s0.insert(ind);
        s[ind] = '0';
        add(ind, -1);
      }
      else{
        s0.erase(ind);
        s[ind] = '1';
        add(ind, 1);

        int r = *s0.lower_bound(ind);
        int l = *(--s0.lower_bound(ind));
        
        //cout << " gl: " << l << ' ' << " gr : " << r << '\n';

        upd(1,1,n,l+1,ind,ind,r-1,-i);
      }
    }
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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