oj.uz

Submission #295599

# Submission time Handle Problem Language Result Execution time Memory
295599 2020-09-09T18:59:26 Z WLZ Street Lamps (APIO19_street_lamps) C++14
20 / 100
 3282 ms 70928 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++;
  }
  if (i == j) {
    seg[idx].val += val;
    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);
  }
  seg[idx].val = 0;
  if (seg[idx].l != -1) {
    seg[idx].val += seg[seg[idx].l].val;
  }
  if (seg[idx].r != -1) {
    seg[idx].val += seg[seg[idx].r].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(1600000, {-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, it->first, it->second, it->second, cur + 1);
        add(it->first, it->first, x, x, -cur - 1);
        add(x + 1, x + 1, it->second, 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};
        /*for (int i = 1; i <= n + 2; i++) {
          for (int j = 1; j <= n + 2; j++) {
            cout << query(i, j) << ' ';
          }
          cout << endl;
        }*/
        add(i_1, i_1, j_2, j_2, -cur - 1);
        add(i_1, i_1, j_1, j_1, cur + 1);
        add(i_2, i_2, j_2, j_2, cur + 1);
        /*for (int i = 1; i <= n + 2; i++) {
          for (int j = 1; j <= n + 2; j++) {
            cout << query(i, j) << ' ';
          }
          cout << endl;
        }*/
        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 12 ms 19072 KB Output is correct
2 Correct 12 ms 19200 KB Output is correct
3 Correct 12 ms 19072 KB Output is correct
4 Correct 13 ms 19072 KB Output is correct
5 Correct 13 ms 19072 KB Output is correct
6 Correct 13 ms 19072 KB Output is correct
7 Correct 12 ms 19072 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 23512 KB Output is correct
2 Correct 1623 ms 23800 KB Output is correct
3 Correct 3282 ms 24696 KB Output is correct
4 Runtime error 561 ms 70924 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 19200 KB Output is correct
2 Correct 24 ms 19200 KB Output is correct
3 Correct 19 ms 19200 KB Output is correct
4 Correct 13 ms 19200 KB Output is correct
5 Runtime error 660 ms 70928 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19200 KB Output is correct
2 Correct 20 ms 19200 KB Output is correct
3 Correct 22 ms 19200 KB Output is correct
4 Correct 27 ms 19200 KB Output is correct
5 Runtime error 554 ms 70820 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19072 KB Output is correct
2 Correct 12 ms 19200 KB Output is correct
3 Correct 12 ms 19072 KB Output is correct
4 Correct 13 ms 19072 KB Output is correct
5 Correct 13 ms 19072 KB Output is correct
6 Correct 13 ms 19072 KB Output is correct
7 Correct 12 ms 19072 KB Output is correct
8 Correct 1103 ms 23512 KB Output is correct
9 Correct 1623 ms 23800 KB Output is correct
10 Correct 3282 ms 24696 KB Output is correct
11 Runtime error 561 ms 70924 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -