oj.uz

Submission #295641

# Submission time Handle Problem Language Result Execution time Memory
295641 2020-09-09T19:26:40 Z WLZ Street Lamps (APIO19_street_lamps) C++14
100 / 100
 4898 ms 210828 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct node {
  int l, r, val;
};

int n, q, cnt = 0;
vector<node> seg;
vector<int> root;

void _update(int &idx, int i, int j, int pos, int val) {
  if (idx == -1) {
    idx = cnt++;
  }
  seg[idx].val += val;
  if (i == j) {
    return;
  }
  int mid = (i + j) / 2;
  if (mid >= pos) {
    _update(seg[idx].l, i, mid, pos, val);
  } else {
    _update(seg[idx].r, mid + 1, j, pos, val);
  }
}

int _query(int idx, int i, int j, int l, int r) {
  if (idx == -1 || i > r || j < l) {
    return 0;
  }
  if (i >= l && j <= r) {
    return seg[idx].val;
  }
  return _query(seg[idx].l, i, (i + j) / 2, l, r) + _query(seg[idx].r, (i + j) / 2 + 1, j, l, r);
}

void update(int i, int j, int val) {
  for (; i <= n + 2; i += i & -i) {
    _update(root[i], 1, n + 2, j, val);
  }
}

int query(int i, int j) {
  int ans = 0;
  for (; i > 0; i -= i & -i) {
    ans += _query(root[i], 1, n + 2, 1, j);
  }
  return ans;
}

void add(int i_1, int j_1, int i_2, int j_2, int val) {
  update(i_1, j_1, val);
  update(i_1, j_2 + 1, -val);
  update(i_2 + 1, j_1, -val);
  update(i_2 + 1, j_2 + 1, val);
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  set< pair<int, int>, comp> st;
  for (int i = 1; i <= n + 1; i++) {
    st.insert({i, i});
  }
  string s;
  cin >> s;
  for (int i = 1; i <= n; i++) {
    if (s[i - 1] == '1') {
      auto it = st.upper_bound({0, i});
      pair<int, int> tmp = {prev(it)->first, it->second};
      st.erase(prev(it)); st.erase(it);
      st.insert(tmp);
    }
  }
  root.assign(n + 3, -1);
  seg.assign(16000000, {-1, -1, 0});
  for (auto& p : st) {
    add(p.first, p.first, p.second, p.second, -1);
  }
  for (int cur = 1; cur <= q; cur++) {
    string t;
    cin >> t;
    if (t == "query") {
      int l, r;
      cin >> l >> r;
      int ans = query(l, r);
      if (st.lower_bound({0, l}) == st.lower_bound({0, r})) {
        ans += cur + 1;
      }
      cout << ans << '\n';
    } else {
      int x;
      cin >> x;
      if (s[x - 1] == '1') {
        auto it = st.lower_bound({0, x});
        pair<int, int> tmp_1 = {it->first, x}, tmp_2 = {x + 1, it->second};
        add(it->first, x + 1, x, it->second, cur + 1);
        st.erase({it->first, it->second});
        st.insert(tmp_1); st.insert(tmp_2);
        s[x - 1] = '0';
      } else {
        auto it = st.upper_bound({0, x});
        int i_1 = prev(it)->first, j_1 = prev(it)->second, i_2 = it->first, j_2 = it->second;
        pair<int, int> tmp = {i_1, j_2};
        add(i_1, i_2, j_1, j_2, -cur - 1);
        st.erase({i_1, j_1}); st.erase({i_2, j_2});
        st.insert(tmp);
        s[x - 1] = '1';
      }
    }
  }
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 188280 KB Output is correct
2 Correct 112 ms 188156 KB Output is correct
3 Correct 110 ms 188152 KB Output is correct
4 Correct 110 ms 188152 KB Output is correct
5 Correct 112 ms 188152 KB Output is correct
6 Correct 112 ms 188152 KB Output is correct
7 Correct 111 ms 188152 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 189176 KB Output is correct
2 Correct 538 ms 189336 KB Output is correct
3 Correct 897 ms 189448 KB Output is correct
4 Correct 3248 ms 205032 KB Output is correct
5 Correct 2846 ms 210392 KB Output is correct
6 Correct 3472 ms 209676 KB Output is correct
7 Correct 3164 ms 210572 KB Output is correct
8 Correct 404 ms 210828 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 188280 KB Output is correct
2 Correct 117 ms 188280 KB Output is correct
3 Correct 115 ms 188280 KB Output is correct
4 Correct 113 ms 188400 KB Output is correct
5 Correct 4898 ms 207116 KB Output is correct
6 Correct 3792 ms 208948 KB Output is correct
7 Correct 2636 ms 209516 KB Output is correct
8 Correct 408 ms 210752 KB Output is correct
9 Correct 221 ms 191864 KB Output is correct
10 Correct 229 ms 192120 KB Output is correct
11 Correct 222 ms 192372 KB Output is correct
12 Correct 2792 ms 210472 KB Output is correct
13 Correct 394 ms 210700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 188296 KB Output is correct
2 Correct 115 ms 188280 KB Output is correct
3 Correct 120 ms 188240 KB Output is correct
4 Correct 116 ms 188280 KB Output is correct
5 Correct 1869 ms 204704 KB Output is correct
6 Correct 2509 ms 204812 KB Output is correct
7 Correct 3211 ms 206892 KB Output is correct
8 Correct 4091 ms 208176 KB Output is correct
9 Correct 640 ms 191736 KB Output is correct
10 Correct 553 ms 191204 KB Output is correct
11 Correct 616 ms 191864 KB Output is correct
12 Correct 580 ms 191232 KB Output is correct
13 Correct 613 ms 191828 KB Output is correct
14 Correct 546 ms 191224 KB Output is correct
15 Correct 2709 ms 210700 KB Output is correct
16 Correct 401 ms 210820 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 188280 KB Output is correct
2 Correct 112 ms 188156 KB Output is correct
3 Correct 110 ms 188152 KB Output is correct
4 Correct 110 ms 188152 KB Output is correct
5 Correct 112 ms 188152 KB Output is correct
6 Correct 112 ms 188152 KB Output is correct
7 Correct 111 ms 188152 KB Output is correct
8 Correct 428 ms 189176 KB Output is correct
9 Correct 538 ms 189336 KB Output is correct
10 Correct 897 ms 189448 KB Output is correct
11 Correct 3248 ms 205032 KB Output is correct
12 Correct 2846 ms 210392 KB Output is correct
13 Correct 3472 ms 209676 KB Output is correct
14 Correct 3164 ms 210572 KB Output is correct
15 Correct 404 ms 210828 KB Output is correct
16 Correct 118 ms 188280 KB Output is correct
17 Correct 117 ms 188280 KB Output is correct
18 Correct 115 ms 188280 KB Output is correct
19 Correct 113 ms 188400 KB Output is correct
20 Correct 4898 ms 207116 KB Output is correct
21 Correct 3792 ms 208948 KB Output is correct
22 Correct 2636 ms 209516 KB Output is correct
23 Correct 408 ms 210752 KB Output is correct
24 Correct 221 ms 191864 KB Output is correct
25 Correct 229 ms 192120 KB Output is correct
26 Correct 222 ms 192372 KB Output is correct
27 Correct 2792 ms 210472 KB Output is correct
28 Correct 394 ms 210700 KB Output is correct
29 Correct 114 ms 188296 KB Output is correct
30 Correct 115 ms 188280 KB Output is correct
31 Correct 120 ms 188240 KB Output is correct
32 Correct 116 ms 188280 KB Output is correct
33 Correct 1869 ms 204704 KB Output is correct
34 Correct 2509 ms 204812 KB Output is correct
35 Correct 3211 ms 206892 KB Output is correct
36 Correct 4091 ms 208176 KB Output is correct
37 Correct 640 ms 191736 KB Output is correct
38 Correct 553 ms 191204 KB Output is correct
39 Correct 616 ms 191864 KB Output is correct
40 Correct 580 ms 191232 KB Output is correct
41 Correct 613 ms 191828 KB Output is correct
42 Correct 546 ms 191224 KB Output is correct
43 Correct 2709 ms 210700 KB Output is correct
44 Correct 401 ms 210820 KB Output is correct
45 Correct 228 ms 190584 KB Output is correct
46 Correct 320 ms 190712 KB Output is correct
47 Correct 1404 ms 197152 KB Output is correct
48 Correct 3002 ms 209392 KB Output is correct
49 Correct 239 ms 192376 KB Output is correct
50 Correct 239 ms 192248 KB Output is correct
51 Correct 233 ms 192632 KB Output is correct
52 Correct 248 ms 192832 KB Output is correct
53 Correct 249 ms 192888 KB Output is correct
54 Correct 243 ms 192760 KB Output is correct