oj.uz

Submission #308268

# Submission time Handle Problem Language Result Execution time Memory
308268 2020-09-30T16:50:31 Z WLZ Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1681 ms 68920 KB 
#include <bits/stdc++.h>
using namespace std;

struct comp {
  inline bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second < b.second;
  }
};

struct event {
  int x, y_1, y_2, val, idx;
};

template<typename T>
class fenwick_tree {
  private:
    int n;
    vector<T> fenw;
    stack<int> st;
  public:
    fenwick_tree(int _n) : n(_n) {
      fenw.resize(n);
    }

    size_t size() {
      return n;
    }

    void update(int x, T val) {
      while (x < n) {
        fenw[x] += val;
        st.push(x);
        x |= (x + 1);
      }
    }

    T query(int x) {
      T ans = 0;
      while (x >= 0) {
        ans += fenw[x];
        x = (x & (x + 1)) - 1;
      }
      return ans;
    }

    void update(int x, int y, T val) {
      update(x, val);
      if (y < n - 1) {
        update(y + 1, -val);
      }
    }

    void reset() {
      while (!st.empty()) {
        fenw[st.top()] = 0;
        st.pop();
      }
    }
};

vector<int> ans;
vector<event> events, sorted_events;
fenwick_tree<int> fenw(0);

void add(int x_1, int y_1, int x_2, int y_2, int val, int idx) {
  events.push_back({x_1, y_1, y_2, val, idx});
  events.push_back({x_2 + 1, y_1, y_2, -val, idx});
}

void solve(int l, int r) {
  if (l + 1 == r) {
    return;
  }
  int mid = (l + r) / 2;
  solve(l, mid);
  solve(mid, r);
  int i = l, j = mid, cur = l;
  while (i < mid && j < r) {
    if (events[i].x <= events[j].x) {
      if (events[i].y_2 != -1) {
        fenw.update(events[i].y_1, events[i].y_2, events[i].val);
      }
      sorted_events[cur++] = events[i++];
    } else {
      if (events[j].y_2 == -1) {
        ans[events[j].idx] += fenw.query(events[j].y_1);
      }
      sorted_events[cur++] = events[j++];
    }
  }
  while (j < r) {
    if (events[j].y_2 == -1) {
      ans[events[j].idx] += fenw.query(events[j].y_1);
    }
    sorted_events[cur++] = events[j++];
  }
  while (i < mid) {
    sorted_events[cur++] = events[i++];
  }
  for (int t = l; t < r; t++) {
    events[t] = sorted_events[t];
  }
  fenw.reset();
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set< pair<int, int>, comp> st;
  for (int i = 1; i <= n + 1; i++) {
    st.insert({i, i});
  }
  for (int i = 1; i <= n; i++) {
    if (s[i - 1] == '1') {
      auto it = st.lower_bound({0, i});
      pair<int, int> tmp = {it->first, i + 1};
      st.erase(it); st.erase({i + 1, i + 1});
      st.insert(tmp);
    }
  }
  ans.assign(q + 1, -1);
  string type;
  for (int t = 1; t <= q; t++) {
    cin >> type;
    if (type == "toggle") {
      int i;
      cin >> i;
      if (s[i - 1] == '0') {
        s[i - 1] = '1';
        auto it = st.lower_bound({0, i});
        int x_1 = it->first, y_1 = it->second, x_2 = next(it)->first, y_2 = next(it)->second;
        pair<int, int> tmp = {x_1, y_2};
        add(x_1, x_2, y_1, y_2, -t, t);
        st.erase({x_1, y_1}); st.erase({x_2, y_2});
        st.insert(tmp);
      } else {
        s[i - 1] = '0';
        auto it = st.lower_bound({0, i + 1});
        int x = it->first, y = it->second;
        add(x, i + 1, i, y, t, t);
        st.erase({x, y});
        st.insert({x, i}); st.insert({i + 1, y});
      }
    } else {
      int a, b;
      cin >> a >> b;
      ans[t] = 0;
      if (st.lower_bound({0, a}) == st.lower_bound({0, b})) {
        ans[t] = t;
      }
      events.push_back({a, b, -1, -1, t});
    }
  }
  fenw = fenwick_tree<int>(n + 2);
  sorted_events.resize((int) events.size()); 
  solve(0, (int) events.size());
  for (int i = 1; i <= q; i++) {
    if (ans[i] != -1) {
      cout << ans[i] << '\n';
    }
  }
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 27728 KB Output is correct
2 Correct 523 ms 29576 KB Output is correct
3 Correct 665 ms 32592 KB Output is correct
4 Correct 1198 ms 52856 KB Output is correct
5 Correct 1020 ms 35752 KB Output is correct
6 Correct 1292 ms 60712 KB Output is correct
7 Correct 594 ms 35532 KB Output is correct
8 Correct 406 ms 28556 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1597 ms 50192 KB Output is correct
6 Correct 1333 ms 40104 KB Output is correct
7 Correct 1058 ms 29500 KB Output is correct
8 Correct 402 ms 22668 KB Output is correct
9 Correct 130 ms 11740 KB Output is correct
10 Correct 147 ms 12952 KB Output is correct
11 Correct 145 ms 12884 KB Output is correct
12 Correct 680 ms 29560 KB Output is correct
13 Correct 409 ms 22668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 736 ms 35936 KB Output is correct
6 Correct 1034 ms 52912 KB Output is correct
7 Correct 1310 ms 60388 KB Output is correct
8 Correct 1681 ms 68920 KB Output is correct
9 Correct 613 ms 35564 KB Output is correct
10 Correct 620 ms 36728 KB Output is correct
11 Correct 617 ms 35536 KB Output is correct
12 Correct 617 ms 36688 KB Output is correct
13 Correct 611 ms 35528 KB Output is correct
14 Correct 621 ms 36696 KB Output is correct
15 Correct 695 ms 35556 KB Output is correct
16 Correct 413 ms 28684 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 454 ms 27728 KB Output is correct
9 Correct 523 ms 29576 KB Output is correct
10 Correct 665 ms 32592 KB Output is correct
11 Correct 1198 ms 52856 KB Output is correct
12 Correct 1020 ms 35752 KB Output is correct
13 Correct 1292 ms 60712 KB Output is correct
14 Correct 594 ms 35532 KB Output is correct
15 Correct 406 ms 28556 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 508 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 1597 ms 50192 KB Output is correct
21 Correct 1333 ms 40104 KB Output is correct
22 Correct 1058 ms 29500 KB Output is correct
23 Correct 402 ms 22668 KB Output is correct
24 Correct 130 ms 11740 KB Output is correct
25 Correct 147 ms 12952 KB Output is correct
26 Correct 145 ms 12884 KB Output is correct
27 Correct 680 ms 29560 KB Output is correct
28 Correct 409 ms 22668 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 2 ms 512 KB Output is correct
32 Correct 3 ms 512 KB Output is correct
33 Correct 736 ms 35936 KB Output is correct
34 Correct 1034 ms 52912 KB Output is correct
35 Correct 1310 ms 60388 KB Output is correct
36 Correct 1681 ms 68920 KB Output is correct
37 Correct 613 ms 35564 KB Output is correct
38 Correct 620 ms 36728 KB Output is correct
39 Correct 617 ms 35536 KB Output is correct
40 Correct 617 ms 36688 KB Output is correct
41 Correct 611 ms 35528 KB Output is correct
42 Correct 621 ms 36696 KB Output is correct
43 Correct 695 ms 35556 KB Output is correct
44 Correct 413 ms 28684 KB Output is correct
45 Correct 229 ms 17108 KB Output is correct
46 Correct 313 ms 18256 KB Output is correct
47 Correct 617 ms 28752 KB Output is correct
48 Correct 1228 ms 52136 KB Output is correct
49 Correct 168 ms 17616 KB Output is correct
50 Correct 167 ms 17488 KB Output is correct
51 Correct 172 ms 17748 KB Output is correct
52 Correct 177 ms 18148 KB Output is correct
53 Correct 179 ms 18000 KB Output is correct
54 Correct 177 ms 18000 KB Output is correct