Submission #892260

#	Time	Username	Problem	Language	Result	Execution time	Memory
892260		tch1cherin	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	1531 ms	79704 KiB

street_lamps

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

struct fenwick {
  int size;
  vector<int> tree;
  int sum;
  vector<int> updates;

  fenwick() {}

  fenwick(int n) : size(n), tree(n + 1), sum(0) {}

  void update(int i, int v) {
    sum += v;
    for (i++; i <= size; i += i & -i) {
      updates.push_back(i);
      tree[i] += v;
    }
  }

  int prefix_query(int r) {
    int ans = 0;
    for (; r > 0; r -= r & -r) {
      ans += tree[r];
    }
    return ans;
  }

  int suffix_query(int l) {
    return sum - prefix_query(l);
  }

  void rollback() {
    for (int i : updates) {
      tree[i] = 0;
    }
    sum = 0;
    updates = vector<int>();
  }
};

struct query {
  int x, y, tx, ty;
  int pos;
};

struct modification {
  int x, y, t;
};

fenwick F, Fc;

void CDQ(vector<query>& queries, vector<int>& answers, int L, int R) {
  if (R - L == 1) {
    return;
  }
  int M = (L + R) / 2;
  CDQ(queries, answers, L, M);
  CDQ(queries, answers, M, R);
  {
    vector<array<int, 4>> events;
    for (int i = L; i < M; i++) {
      if (queries[i].pos == -1) {
        events.push_back({queries[i].y, queries[i].ty, 0, queries[i].ty - queries[i].tx});
      }
    }
    for (int i = M; i < R; i++) {
      if (queries[i].pos != -1) {
        events.push_back({queries[i].y, queries[i].ty, 1, queries[i].pos});
      }
    }
    sort(events.begin(), events.end(), [](array<int, 4> a, array<int, 4> b) {
      return a[0] != b[0] ? a[0] > b[0] : (a[1] != b[1] ? a[1] < b[1] : a[2] < b[2]);
    });
    for (auto [y, ty, type, value] : events) {
      if (type == 0) {
        F.update(ty, value);
      } else {
        answers[value] += F.prefix_query(ty + 1); 
      }
    }
    F.rollback();
  }
  {
    vector<array<int, 4>> events;
    for (int i = L; i < M; i++) {
      if (queries[i].pos == -1) {
        events.push_back({queries[i].tx, 0, queries[i].y, -queries[i].tx});
        events.push_back({queries[i].ty, -1, queries[i].y, queries[i].tx});
      }
    }
    for (int i = M; i < R; i++) {
      if (queries[i].pos != -1) {
        events.push_back({queries[i].tx, 1, queries[i].y, queries[i].pos});
      }
    }
    sort(events.begin(), events.end());
    for (auto [x, type, y, value] : events) {
      if (type <= 0) {
        F.update(y, value);
        Fc.update(y, type == 0 ? +1 : -1);
      } else {
        answers[value] += 1LL * Fc.suffix_query(y) * x + F.suffix_query(y); 
      }
    }
    F.rollback();
    Fc.rollback();
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<modification> modifications;
  set<pair<int, int>> segments;
  int T = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') {
      continue;
    }
    int j = i + 1;
    while (j < n && s[j] == '1') {
      j++;
    }
    modifications.push_back({i, j - 1, T});
    segments.insert({i, j - 1});
    i = j - 1;
  }
  vector<query> queries;
  int cnt_q = 0;
  while (q--) {
    T++;
    string type;
    cin >> type;
    if (type == "toggle") {
      int pos;
      cin >> pos;
      pos--;
      if (s[pos] == '0') {
        s[pos] = '1';
        if (segments.empty()) {
          modifications.push_back({pos, pos, T});
          segments.insert({pos, pos});
        } else {
          auto it = segments.lower_bound({pos, -1});
          bool left_merge = it != segments.begin() && prev(it)->second == pos - 1;
          bool right_merge = it != segments.end() && it->first == pos + 1;
          if (left_merge && right_merge) {
            int L = prev(it)->first, R = it->second;
            modifications.push_back({prev(it)->first, prev(it)->second, T});
            segments.erase({prev(it)->first, prev(it)->second});
            modifications.push_back({it->first, it->second, T});
            segments.erase({it->first, it->second});
            modifications.push_back({L, R, T});
            segments.insert({L, R});
          } else if (left_merge) {
            int L = prev(it)->first, R = pos;
            modifications.push_back({prev(it)->first, prev(it)->second, T});
            segments.erase({prev(it)->first, prev(it)->second});
            modifications.push_back({L, R, T});
            segments.insert({L, R});
          } else if (right_merge) {
            int L = pos, R = it->second;
            modifications.push_back({it->first, it->second, T});
            segments.erase({it->first, it->second});
            modifications.push_back({L, R, T});
            segments.insert({L, R});
          } else {
            modifications.push_back({pos, pos, T});
            segments.insert({pos, pos});
          }
        }
      } else {
        s[pos] = 0;
        auto it = prev(segments.lower_bound({pos, INT_MAX}));
        int L = it->first, R = it->second;
        modifications.push_back({L, R, T});
        segments.erase({L, R});
        if (L <= pos - 1) {
          modifications.push_back({L, pos - 1, T});
          segments.insert({L, pos - 1});
        }
        if (pos + 1 <= R) {
          modifications.push_back({pos + 1, R, T});
          segments.insert({pos + 1, R});
        }
      }
    } else {
      int a, b;
      cin >> a >> b;
      a--, b -= 2;
      queries.push_back({a, b, T, T, cnt_q++});
    }
  }
  sort(modifications.begin(), modifications.end(), [](modification a, modification b) {
    return a.x != b.x ? a.x < b.x : (a.y != b.y ? a.y < b.y : a.t < b.t);
  });
  int m = (int)modifications.size();
  T++;
  for (int i = 0; i < m; i++) {
    vector<int> times;
    int j = i;
    while (j < m && modifications[i].x == modifications[j].x && modifications[i].y == modifications[j].y) {
      times.push_back(modifications[j++].t);
    }
    times.push_back(T);
    for (int k = 0; k < (int)times.size() - 1; k += 2) {
      queries.push_back({modifications[i].x, modifications[i].y, times[k], times[k + 1], -1});
    }
    i = j - 1;
  }
  F = Fc = fenwick(max(n, T) + 1);
  vector<int> answers(cnt_q);
  sort(queries.begin(), queries.end(), [](query a, query b) {
    return a.x != b.x ? a.x < b.x : (a.y != b.y ? a.y > b.y : (a.tx != b.tx ? a.tx < b.tx : a.ty < b.ty));
  });
  CDQ(queries, answers, 0, (int)queries.size());
  for (int value : answers) {
    cout << value << "\n";
  }
}

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