Submission #855873

#	Time	Username	Problem	Language	Result	Execution time	Memory
855873		NeroZein	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	130 ms	73552 KiB

street_lamps

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

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

const int N = 3e3; 
const int INF = 1e9;  

struct bit {
  vector<int> tr; 
  bit() {
    tr.resize(N);
  }
  void upd(int i, int v) {//point upd
    i++;
    while (i < N) {
      tr[i] += v;
      i += i & -i; 
    }
  }
  int qry(int i) {//prefix till i
    i++;
    int ret = 0;
    while (i) {
      ret += tr[i];
      i -= i & -i; 
    }
    return ret;
  }
  int qry(int l, int r) {
    return qry(r) - qry(l - 1); 
  }
}; 

bit seg[N * 2]; 

void upd(int nd, int l, int r, int p, int x, int v) {
  if (r <= p) {
    seg[nd].upd(x, v);         
  }
  if (l == r) {
    return; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, x, v); 
  } else {
    upd(rs, mid + 1, r, p, x, v); 
  }
}

int qry(int nd, int l, int r, int s, int e, int key) {
  if (l >= s && r <= e) {
    return seg[nd].qry(key);
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e, key); 
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e, key); 
    } else {
      return qry(nd + 1, l, mid, s, e, key) + qry(rs, mid + 1, r, s, e, key); 
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<array<int, 3>> se;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') {
      continue;
    }
    int j = i;
    while (j + 1 < n && s[j + 1] == '1') {
      j++; 
    }
    se.insert({i, j, 0}); 
    i = j; 
  }
  vector<map<int, int>> tmp(n); 
  auto edit_set = [&](int i, int t) {
    if (s[i] == '1') {
      array<int, 3> key = {i, INF, INF};
      auto f = se.upper_bound(key);
      --f;
      //for (int x = (*f)[0]; x <= (*f)[1]; x++) {
        //for (int y = x; y <= (*f)[1]; y++) {
          //tmp[x][y] += t - (*f)[2]; 
        //}
      //}
      int x = (*f)[0], y = (*f)[1]; 
      upd(0, 0, n - 1, y, x, t - (*f)[2]); 
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        se.erase(f); 
        int l = (*f)[0], r = (*f)[1]; 
        se.insert({l, i - 1, t});
        se.insert({i + 1, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        int l = (*f)[0];
        se.erase(f);
        se.insert({l, i - 1, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        int r = (*f)[1];
        se.erase(f);
        se.insert({i + 1, r, t}); 
      } else {
        se.erase(f); 
      }
    } else {
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto pr = se.upper_bound(key);
        --pr;
        key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        int l = (*pr)[0], r = (*nx)[1];
        //for (int x = (*pr)[0]; x <= (*pr)[1]; ++x) {
          //for (int y = x; y <= (*pr)[1]; ++y) {
            //tmp[x][y] += t - (*pr)[2]; 
          //}
        //}
        int x = (*pr)[0], y = (*pr)[1]; 
        upd(0, 0, n - 1, y, x, t - (*pr)[2]); 
        //for (int x = (*nx)[0]; x <= (*nx)[1]; ++x) {
          //for (int y = x; y <= (*nx)[1]; ++y) {
            //tmp[x][y] += t - (*nx)[2]; 
          //}
        //}
        x = (*nx)[0], y = (*nx)[1];
        upd(0, 0, n - 1, y, x, t - (*nx)[2]);
        se.erase(pr);
        se.erase(nx);
        se.insert({l, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto pr = se.upper_bound(key);
        --pr;
        int l = (*pr)[0], r = i; 
        //for (int x = (*pr)[0]; x <= (*pr)[1]; ++x) {
          //for (int y = x; y <= (*pr)[1]; ++y) {
            //tmp[x][y] += t - (*pr)[2]; 
          //}
        //}
        int x = (*pr)[0], y = (*pr)[1]; 
        upd(0, 0, n - 1, y, x, t - (*pr)[2]);
        se.erase(pr); 
        se.insert({l, r, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        //for (int x = (*nx)[0]; x <= (*nx)[1]; ++x) {
          //for (int y = x; y <= (*nx)[1]; ++y) {
            //tmp[x][y] += t - (*nx)[2]; 
          //}
        //}
        int x = (*nx)[0], y = (*nx)[1]; 
        upd(0, 0, n - 1, y, x, t - (*nx)[2]);
        int l = i, r = (*nx)[1];
        se.erase(nx); 
        se.insert({l, r, t}); 
      } else {
        se.insert({i, i, t}); 
      }
    }
    s[i] ^= 1; 
  }; 
  vector<vector<pair<int, int>>> vec(n);
  for (int i = 1; i <= q; ++i) {
    string qs;
    cin >> qs;
    if (qs == "query") {
      int l, r;
      cin >> l >> r;
      --l, r -= 2; 
      int ans = 0; 
      array<int, 3> key = {l, INF, INF}; 
      auto f = se.upper_bound(key);
      if (f != se.begin()) {
        --f; 
        if ((*f)[0] <= l && (*f)[1] >= r) {
          ans += i - (*f)[2];
        }
      }
      cout << ans + qry(0, 0, n - 1, r, n - 1, l) << '\n'; // make query on 2d seg, xs: [l, r], ys: [0, l]
    } else {
      int ind;
      cin >> ind;
      edit_set(ind - 1, i); 
    }
  }
  return 0;
}

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