Submission #1129789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129789		rxlfd314	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3258 ms	26328 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;

template <class T> using vt = vector<T>;
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 300005;
int N, Q, queries[mxN][3];
bool lamp[mxN];

struct BIT {
  int fen[mxN];
  void update(int i, int v) {
    for (++i; i <= N; i += i & -i)
      fen[i] += v;
  }
  int query(int i) {
    int ret = 0;
    for (++i; i > 0; i -= i & -i)
      ret += fen[i];
    return ret;
  }
  int query(int l, int r) {
    return query(r) - query(l-1);
  }
} fen;

multiset<ari3> ranges;
int ans[mxN];
void dnc(const int tl, const int tr) {
  const int tm = tl + tr >> 1;
  vt<ari3> events, rescind, restore;
  FOR(i, tm+(tl<tr), tr)
    if (queries[i][0] == 1)
      events.push_back({queries[i][1], queries[i][2], -i - 1});
  vt<ari2> lamps;
  FOR(x, tl, tm) {
    if (queries[x][0] == 1)
      continue;
    const int i = queries[x][1];
    if (lamp[i]) {
      lamps.push_back({i, 1});
      lamp[i] = 0;
      auto it = prev(ranges.lower_bound({i+1, -1, -1}));
      const auto [l, r, y] = *it;
      events.push_back({l, r, x - max(y, tl-1)});
      if (y < tl)
        restore.push_back({l, r, y});
      ranges.erase(it);
      if (l < i) {
        ranges.insert({l, i-1, x});
        rescind.push_back({l, i-1, x});
      }
      if (r > i) {
        ranges.insert({i+1, r, x});
        rescind.push_back({i+1, r, x}); 
      }
    } else {
      lamps.push_back({i, 0});
      lamp[i] = 1;
      ari3 ins = {i, i, x};
      {
        auto it = ranges.lower_bound({i, -1, -1});
        if (it == ranges.end())
          goto jail;
        const auto [l, r, y] = *it;
        if (l == i + 1) {
          events.push_back({l, r, x - max(y, tl-1)});
          ranges.erase(it);
          ins[1] = r;
          if (y < tl)
            restore.push_back({l, r, y});
        }
      }
      jail:;
      {
        auto it = ranges.lower_bound({i, -1, -1});
        if (it == ranges.begin())
          goto the_asd_clinic;
        it--;
        const auto [l, r, y] = *it;
        if (r == i - 1) {
          events.push_back({l, r, x - max(y, tl-1)});
          ranges.erase(it);
          ins[0] = l;
          if (y < tl)
            restore.push_back({l, r, y});
        }
      }
      the_asd_clinic:;
      ranges.insert(ins);
      rescind.push_back(ins);
    }
  }
  #ifdef DEBUG
  cout << "new ranges " << tl << ' ' << tr << ":\n";
  for (auto [l, r, _] : ranges)
    cout << l << ' ' << r << '\n';
  #endif
  sort(all(events), [&](const ari3 &a, const ari3 &b) {
    if (a[0] != b[0])
      return a[0] < b[0];
    return a[2] > b[2];
  });
  for (auto [l, r, v] : events) {
    if (v < 0) {
      v = -v - 1;
      ans[v] += fen.query(r, N-1);
      auto it = ranges.lower_bound({r+1, -1, -1});
      if (it == begin(ranges))
        continue;
      const auto [a, b, t] = *prev(it);
      if (a <= l && r <= b)
        ans[v] += tm - max(t, tl-1);
      #ifdef DEBUG
      cout << "query " << tl << ' ' << tr << ": " << l << ' ' << r << ' ' << v << '\n';
      #endif
    } else {
      fen.update(r, v);
      #ifdef DEBUG
      cout << "watesiggma " << tl << ' ' << tr << ": " << l << ' ' << r << ' ' << v << '\n';
      #endif
    }
  }
  for (auto [l, r, v] : events)
    if (v >= 0)
      fen.update(r, -v);
  if (tl < tr)
    dnc(tm+1, tr);
  
  for (auto &i : rescind)
    if (ranges.find(i) != ranges.end())
      ranges.erase(ranges.find(i));
  for (auto &i : restore)
    ranges.insert(i);
  reverse(all(lamps));
  for (auto &[a, b] : lamps)
    lamp[a] = b;
  #ifdef DEBUG
  cout << "fixed ranges 1: " << tl << ' ' << tr << ":\n";
  for (auto [l, r, _] : ranges)
    cout << l << ' ' << r << '\n';
  #endif
  
  if (tl < tr)
    dnc(tl, tm);
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> Q;
  FOR(i, 0, N-1) {
    char c; cin >> c;
    lamp[i] = c - '0';
  }
  FOR(i, 0, Q-1) {
    string qt;
    cin >> qt >> queries[i][1], queries[i][1]--;
    if (qt == "query") {
      queries[i][0] = 1;
      cin >> queries[i][2], queries[i][2] -= 2;
    }
  }
  int L = N;
  FOR(i, 0, N-1) {
    if (lamp[i]) {
      L = min(L, i);
    } else {
      if (L < i)
        ranges.insert({L, i-1, -1});
      L = N;
    }
  }
  if (L < N)
    ranges.insert({L, N-1, -1});
  #ifdef DEBUG
  cout << "ranges:\n";
  for (auto [l, r, _] : ranges)
    cout << l << ' ' << r << '\n';
  #endif
  dnc(0, Q-1);
  FOR(i, 0, Q-1)
    if (queries[i][0] == 1)
      cout << ans[i] << '\n';
}

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