Submission #1095073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095073		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1223 ms	155800 KiB

street_lamps

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <set>
#include <functional>
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const int INF = 1e9;
const int NMAX = 3e5;

struct Query {
  int x, y;
};

std::string s;

std::set<int> lt;

Query Q[NMAX + 1];
int answer[NMAX + 1];

int rt[NMAX + 1];
int tt[NMAX + 1];

std::vector<std::tuple<int, int, int>> events;

int n;

void finish(int l, int t) {
  events.push_back({l, rt[l], t - tt[l]});
  tt[l] = t;
}

void printLeft() {
  std::cout << "\nLEFT POINTS:\n";
  for (const auto &p : lt) {
    std::cout << p << ' ';
  }
  std::cout << '\n';
}

void toggle(int pos, int t) {
  // std::cout << "\n\n\n";
  // std::cout << debug(t);
  // printLeft();
  if (s[pos] == 0) {
    auto it = lt.lower_bound(pos);
    int st = *prev(it);
    int dr = *it;
    if (st != -1 && dr == pos + 1 && rt[st] == pos - 1) {    
      finish(st, t);
      finish(dr, t);
      lt.erase(dr);
      rt[st] = rt[dr];
    } else if (dr == pos + 1) {
      finish(dr, t);
      lt.erase(dr);
      lt.insert(pos);
      rt[pos] = rt[dr];
      tt[pos] = t;
    } else if (st != -1 && rt[st] == pos - 1) {
      finish(st, t);
      rt[st] = pos;
    } else {
      rt[pos] = pos;
      lt.insert(pos);
      tt[pos] = t;
    }
  } else {
    // std::cout << debug(t);
    // std::cout << debug(pos);
    // printLeft();
    // if (t == 4) {
    //   std::cout << "HERE\n";
    // }
    auto it = lt.upper_bound(pos);
    it = prev(it);
    auto me = *it;
    finish(me, t);
    if (pos != rt[me]) {
      lt.insert(pos + 1);
      rt[pos + 1] = rt[me];
      tt[pos + 1] = t;
    }
    if (me == pos) {
      lt.erase(pos);
    } else {
     rt[me] = pos - 1;
      tt[me] = t;
    }
  }
}

void query(int l, int r, int t) {
  events.push_back({l, r, -(t + 1)});
  int me = *std::prev(lt.upper_bound(l));
  if (me != -1 && rt[me] >= r) {
    answer[t] += t - tt[me];
  }
}

std::vector<int> ys[NMAX + 1];
std::vector<ll> aib[NMAX + 1];

void updateDry(int x, int y, int v = 0) {
  for (; x <= NMAX; x += x & -x) {
    ys[x].push_back(y);
  }
}
void queryDry(int x, int y) {
  for (; x > 0; x -= x & -x) {
    ys[x].push_back(y);
  }
}
void build() {
  for (int i = 1; i <= NMAX; i++) {
    ys[i].push_back(0);
    ys[i].push_back(NMAX + 1);
    std::sort(ys[i].begin(), ys[i].end());
    ys[i].erase(std::unique(ys[i].begin(), ys[i].end()), ys[i].end());
    aib[i].resize((int) ys[i].size() + 1, 0);
  }
}

void updateWet(int x, int y, int v) {
  for (; x <= NMAX; x += x & -x) {
    for (int j = std::lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin(); j > 0; j -= j & -j) {
      aib[x][j] += v;
    }
  }
}
int queryWet(int x, int y) {
  int ret = 0;
  for (; x > 0; x -= x & -x) {
    for (int j = std::lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin(); j <= (int) ys[x].size(); j += j & -j) {
      ret += aib[x][j];
    }
  }
  return ret;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int q;
  std::cin >> n >> q;

  std::cin >> s;
  s = '$' + s;

  lt.insert(-1);
  lt.insert(-2);
  lt.insert(n + 2);
  lt.insert(n + 3);
  
  for (int i = 1; i <= n; i++) {
    s[i] -= '0';
    if (s[i] == 1) {
      s[i] ^= 1;
      toggle(i, 0);
      s[i] ^= 1;
    }
  }

  for (int i = 1; i <= q; i++) {
    std::string type;
    std::cin >> type;
    if (type == "toggle") {
      std::cin >> Q[i].x;
      Q[i].y = -1;
      answer[i] = -1;
      toggle(Q[i].x, i);
      s[Q[i].x] ^= 1;
    } else {
      std::cin >> Q[i].x >> Q[i].y;
      Q[i].y--;
      answer[i] = 0;
      query(Q[i].x, Q[i].y, i);
    }
    // std::cout << "PASS\n";
  }
  
  for (const auto &[l, r, t] : events) {
    if (t >= 0) { // update
      updateDry(l, r, t);
    } else { // query
      queryDry(l, r);
    }
  }

  build();

  for (const auto &[l, r, t] : events) {
    if (t >= 0) {
      // std::cout << "update " << l << ' ' << r << ' ' << t << '\n';
      updateWet(l, r, t);
    } else {
      assert(1 <= -(t + 1) && -(t + 1) <= q);
      answer[-(t + 1)] += queryWet(l, r);
    }
  }

  for (int i = 1; i <= q; i++) {
    if (answer[i] != -1) {
      std::cout << answer[i] << '\n';
    }
  }

  return 0;
}

Compilation message (stderr)

street_lamps.cpp:8:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    8 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

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