oj.uz

Submission #892260

# Submission time Handle Problem Language Result Execution time Memory
892260 2023-12-25T06:13:11 Z tch1cherin Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1531 ms 79704 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 888 ms 61800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1511 ms 79704 KB Output is correct
6 Correct 1531 ms 77080 KB Output is correct
7 Correct 1295 ms 50676 KB Output is correct
8 Correct 547 ms 25860 KB Output is correct
9 Correct 313 ms 15544 KB Output is correct
10 Correct 341 ms 21804 KB Output is correct
11 Correct 356 ms 20892 KB Output is correct
12 Correct 551 ms 24068 KB Output is correct
13 Correct 556 ms 26636 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -