Submission #1095023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095023		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	5071 ms	12620 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;

std::string s;

std::set<int> lt;

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

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

int n;

void finish(int l, int t) {
  // assert(l >= 1);
  assert(l <= n);
  collected.push_back({l, rt[l], t - tt[l]});
  tt[l] = t;
}

void toggle(int pos, int t) {
  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 {
    auto it = lt.upper_bound(pos);
    it = prev(it);
    auto me = *it;
    finish(me, t);
    if (me != rt[pos]) {
      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;
    }
  }
}

int query(int l, int r, int t) {
  r--;
  int answer = 0;
  int me = *std::prev(lt.upper_bound(l));
  if (me != -1 && rt[me] >= r) {
    answer += t - tt[me];
  }
  for (const auto &[ll, rr, T] : collected) { 
    if (ll <= l && r <= rr) {
      answer += T;
    }
  }
  return answer;
}

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") {
      int p;
      std::cin >> p;
      toggle(p, i);
      s[p] ^= 1;
    } else {
      int l, r;
      std::cin >> l >> r;
      std::cout << query(l, r, 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: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20