제출 #1191503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191503		epicci23	가로등 (APIO19_street_lamps)	C++20	0 / 100	5091 ms	133880 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;
}

struct Node{
  int id, lazy, ans, pri;
  Node* lc;
  Node* rc;
  Node(int _id){
   id = _id;
   lc = rc = NULL;
   lazy = ans = 0;
   pri = rng();
  }
};

void recalc(Node* rt){
  if(!rt) return;
  if(rt -> lazy == 0) return;
  rt -> ans += rt -> lazy;
  if(rt -> lc) rt -> lc -> lazy += rt -> lazy;
  if(rt -> rc) rt -> rc -> lazy += rt -> lazy;
  rt -> lazy = 0;
}

Node* merge(Node* a,Node* b){
  recalc(a), recalc(b);
  if(!a || !b) return (!a ? b : a);
  if(a -> pri > b -> pri){
    a -> rc = merge(a -> rc, b);
    recalc(a);
    return a;
  }
  b -> lc = merge(a, b -> lc);
  recalc(b);
  return b;
}

array<Node*,2> split_by_r(Node* a,int k){
  recalc(a);
  if(!a) return {NULL, NULL};
  if(v[(a -> id)][0] > k){
    auto X = split_by_r(a -> lc, k);
    a -> lc = X[1];
    recalc(a);
    return {X[0], a};
  }
  auto X = split_by_r(a -> rc, k);
  a -> rc = X[0];
  recalc(a);
  return {a, X[1]};
}

array<Node*,2> split_by_id(Node* a,int k){
  recalc(a);
  if(!a) return {NULL, NULL};
  if(a -> id > k){
    auto X = split_by_id(a -> lc, k);
    a -> lc = X[1];
    recalc(a);
    return {X[0], a};
  }
  auto X = split_by_id(a -> rc, k);
  a -> rc = X[0];
  recalc(a);
  return {a, X[1]};
}

Node* T[4 * N];

void Add_Node(int rt,int l,int r,int id){
  auto X = split_by_id(T[rt], id);
  T[rt] = merge(merge(X[0], new Node(id)), X[1]);

  if(l == r) return;
  int mid = (l + r) / 2;
  Add_Node(rt * 2, l, mid, id), Add_Node(rt * 2 + 1, mid + 1, r, id);
}

void Query(int rt,int l,int r,int id){
  auto X = split_by_id(T[rt], id - 1);
  auto X2 = split_by_id(X[1], id + 1);
  
  if(X2[0]){
    recalc(X2[0]);
    tot += X2[0] -> ans; 
  }
  
  T[rt] = merge(merge(X[0], X2[0]), X2[1]);


  if(l == r) return;
  int mid = (l + r) / 2;
  Query(rt * 2, l, mid, id), 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){
    auto X = split_by_r(T[rt], pl - 1);
    auto X2 = split_by_r(X[1], pr + 1);
    if(X2[0]) X2[0] -> lazy += val;
    T[rt] = merge(merge(X[0], X2[0]), X2[1]);
    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++) T[i] = NULL;

  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: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20