Submission #859608

#	Time	Username	Problem	Language	Result	Execution time	Memory
859608		NeroZein	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	511 ms	39104 KiB

street_lamps

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 3e5 + 5; 

int n, q;
int tree[N]; 
vector<char> c;
vector<int> ans; 
vector<array<int, 3>> qq; 
vector<array<int, 3>> qu[N];
set<array<int, 3>> ranges;

void toggle(int ind, int t) {
  if (c[ind] == '1') {
    array<int, 3> key = {ind, n, n}; 
    auto f = ranges.upper_bound(key);
    --f;
    auto [l, r, val] = *f; 
    if (l < ind) {
      ranges.insert({l, ind - 1, t}); 
    }
    if (ind < r) {
      ranges.insert({ind + 1, r, t}); 
    }
    qu[t].push_back({l, r, t - val}); 
    ranges.erase(f); 
  } else {
    bool pre = ind > 0 && c[ind - 1] == '1';
    bool nx = ind < n - 1 && c[ind + 1] == '1';
    if (nx && pre) {
      array<int, 3> key = {ind, n, n};
      auto f = ranges.upper_bound(key);
      auto [l, r, val] = *f;
      auto [ll, rr, vval] = *prev(f); 
      qu[t].push_back({l, r, t - val});
      qu[t].push_back({ll, rr, t - val}); 
      ranges.erase(prev(f));
      ranges.erase(f); 
      ranges.insert({ll, r, t}); 
    } else if (nx) {
      array<int, 3> key = {ind, n, n};
      auto f = ranges.upper_bound(key);
      auto [l, r, val] = *f;
      qu[t].push_back({l, r, t - val}); 
      ranges.insert({ind, r, t});
      ranges.erase(f); 
    } else if (pre) {
      array<int, 3> key = {ind, n, n};
      auto f = ranges.upper_bound(key);
      --f;
      auto [l, r, val] = *f; 
      qu[t].push_back({l, r, t - val}); 
      ranges.insert({l, ind, t}); 
      ranges.erase(f); 
    } else {
      ranges.insert({ind, ind, t}); 
    }
  }
  c[ind] ^= 1;
}

inline void upd (int id, int v) {
  id++; 
  while (id < N) {
    tree[id] += v;
    id += id & -id;
  }
}

inline long long qry (int id) {
  id++; 
  long long ret = 0; 
  while (id) {
    ret += tree[id];
    id -= id & -id; 
  }
  return ret; 
}

int qry(int l, int r) {
  return qry(r) - qry(l - 1); 
}


void solve(int l, int r) {
  if (l == r) {
    return; 
  }
  int mid = (l + r) / 2;
  vector<array<int, 4>> t; 
  for (int i = l; i <= mid; ++i) {
    for (auto [ll, rr, v] : qu[i]) {
      t.push_back({ll, 0, rr, v});
    }
  }
  for (int i = mid + 1; i <= r; ++i) {
    auto [ll, rr, e] = qq[i];
    if (e) {
      t.push_back({ll, 1, rr, i}); 
    }
  }
  //deb(l) deb(r) deb(t) cout << '\n';
  sort(t.begin(), t.end()); 
  for (int i = 0; i < (int) t.size(); ++i) {
    auto [ll, tp, rr, val] = t[i];
    if (tp == 0) {
      upd(rr, val); 
      //deb(rr) deb(val) cout << '\n';
    } else {
      //deb(rr) deb(qry(rr, n)) cout << '\n';
      ans[val] += qry(rr, n); 
    }
  }
  for (int i = 0; i < (int) t.size(); ++i) {
    auto [ll, tp, rr, val] = t[i];
    if (tp == 0) {
      upd(rr, -val); 
    }
  }
  solve(l, mid);
  solve(mid + 1, r); 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q;
  c.resize(n); 
  for (int i = 0; i < n; ++i) {
    cin >> c[i]; 
  }
  for (int i = 0; i < n; ++i) {
    if (c[i] == '0') {
      continue; 
    }
    int j = i;
    while (j + 1 < n && c[j + 1] == c[j]) {
      j++;
    }
    ranges.insert({i, j, -1}); 
    i = j; 
  }
  qq.resize(q); 
  ans.resize(q); 
  for (int i = 0; i < q; ++i) {
    string qt;
    cin >> qt;
    if (qt[0] == 'q') {
      int x, y;
      cin >> x >> y;
      --x, y -= 2; 
      array<int, 3> key = {x, n, n};
      auto f = ranges.upper_bound(key);
      if (f != ranges.begin()) {
        --f;
        if ((*f)[1] >= y) {
          ans[i] += i - (*f)[2];          
        }
      }
      qq[i] = {x, y, 1}; 
    } else {
      int ind;
      cin >> ind;
      toggle(ind - 1, i); 
    }
  }
  solve(0, q - 1); 
  for (int i = 0; i < q; ++i) {
    if (qq[i][2] == 1) {
      cout << ans[i] << '\n';      
    }
  }
  return 0;
}

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