oj.uz

Submission #189134

# Submission time Handle Problem Language Result Execution time Memory
189134 2020-01-13T21:55:16 Z AlexPop28 Street Lamps (APIO19_street_lamps) C++11
100 / 100
 2992 ms 172412 KB 
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

struct Fenwick {
  int n;
  vector<int> tree;
  Fenwick(int n_ = 0) : n(n_), tree(n + 1) {}
  inline int lsb(int x) {
    return x & -x;
  }
  void Update(int pos, int val) {
    for (++pos; pos <= n; pos += lsb(pos))
      tree[pos] += val;
  }
  void Update(int left, int right, int val) {
    Update(left, val);
    Update(right + 1, -val);
  }
  int Query(int pos) {
    int ans = 0;
    for (++pos; pos; pos -= lsb(pos))
      ans += tree[pos];
    return ans;
  }
};

struct SegmTree {
  int n;
  vector<Fenwick> tree;
  vector<vector<int>> qrs;
  SegmTree(int n_) : n(n_), tree(4 * n), qrs(4 * n) {}
  void Build() {
    for (int node = 0; node < 4 * n; ++node) {
      sort(qrs[node].begin(), qrs[node].end());
      qrs[node].erase(unique(qrs[node].begin(), qrs[node].end()), qrs[node].end());
      tree[node] = Fenwick(qrs[node].size());
    }
  }

  void AddQuery(int node, int left, int right, int a, int b) {
    qrs[node].emplace_back(b);
    if (left == right) return;
    int mid = left + (right - left) / 2;
    if (a <= mid) {
      AddQuery(2 * node + 1, left, mid, a, b);
    } else {
      AddQuery(2 * node + 2, mid + 1, right, a, b);
    }
  }

  void Update(int node, int left, int right, int x, int y, int val) {
    if (qrs[node].empty()) return;
    if (x <= left && right <= y) {
      // vreau queryurile care au capatul dreapta <= y
      // capatul stanga imi e asigurat de aint
      int pos = upper_bound(qrs[node].begin(), qrs[node].end(), y) -
                qrs[node].begin() - 1;
      tree[node].Update(0, pos, val);
      return; 
    }

    int mid = left + (right - left) / 2;
    if (x <= mid) {
      Update(2 * node + 1, left, mid, x, y, val);
    }
    if (mid < y) {
      Update(2 * node + 2, mid + 1, right, x, y, val);
    }
  }

  int Query(int node, int left, int right, int x, int y) {
    if (qrs[node].empty()) return 0;
    int pos = lower_bound(qrs[node].begin(), qrs[node].end(), y) -
              qrs[node].begin();
    int ans = tree[node].Query(pos);
    if (left == right) return ans;
    
    int mid = left + (right - left) / 2;
    if (x <= mid) {
      ans += Query(2 * node + 1, left, mid, x, y);
    } else {
      ans += Query(2 * node + 2, mid + 1, right, x, y);
    }
    return ans;
  }

  void AddQuery(int a, int b) {
    AddQuery(0, 0, n - 1, a, b);
  }

  void TurnOn(int l, int r, int t) {
    Update(0, 0, n - 1, l, r, -t);
  }

  void TurnOff(int l, int r, int t) {
    Update(0, 0, n - 1, l, r, +t);
  }

  int Query(int l, int r) {
    return Query(0, 0, n - 1, l, r); 
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, q; cin >> n >> q;
  string s; cin >> s;
  SegmTree st(n);
  vector<tuple<int, int, int>> qrs(q);
  for (auto &e : qrs) {
    string t; cin >> t;
    if (t[0] == 't') {
      int pos; cin >> pos; --pos;
      e = make_tuple(0, pos, -1);
    } else {
      int a, b; cin >> a >> b; --a, --b, --b;
      e = make_tuple(1, a, b);
      st.AddQuery(a, b);
    }
  }
  st.Build();

  set<pair<int, int>> ones;
  for (int i = 0; i < n; ) {
    if (s[i] == '0') {
      ++i;
    } else {
      int j = i;
      while (i < n && s[i] == '1') ++i;
      ones.emplace(j, i - 1);
    }
  }
   
  for (int t = 1; t <= q; ++t) {
    int type, x, y; tie(type, x, y) = qrs[t - 1];
    if (type == 0) {
      if (s[x] == '0') {
        int l = x, r = x;
        auto it = ones.lower_bound({x, 0});

        if (it != ones.begin()) {
          if (prev(it)->second == x - 1) {
            l = prev(it)->first;
            it = ones.erase(prev(it));
            st.TurnOff(l, x - 1, t);
          }
        }

        if (it != ones.end()) {
          if (it->first == x + 1) {
            r = it->second;
            ones.erase(it);
            st.TurnOff(x + 1, r, t);
          }
        }

        ones.emplace(l, r);
        st.TurnOn(l, r, t);
      } else {
        auto it = ones.upper_bound({x, n}); --it;
        assert(it->first <= x && x <= it->second);
        int l, r; tie(l, r) = *it;

        if (x != l) {
          ones.emplace(l, x - 1);
          st.TurnOn(l, x - 1, t);
        }
        if (x != r) {
          ones.emplace(x + 1, r);
          st.TurnOn(x + 1, r, t);
        }

        ones.erase(it);
        st.TurnOff(l, r, t);
      }
      s[x] ^= '0' ^ '1';
    } else {
      int ans = st.Query(x, y);
      auto it = ones.upper_bound({x, n});
      if (it != ones.begin()) {
        --it;
        assert(it->first <= x);
        if (it->second >= y) {
          ans += t;
        }
      }
      cout << ans << '\n';
    }
  }
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 14304 KB Output is correct
2 Correct 326 ms 15896 KB Output is correct
3 Correct 616 ms 22224 KB Output is correct
4 Correct 2009 ms 147376 KB Output is correct
5 Correct 2177 ms 151216 KB Output is correct
6 Correct 1582 ms 140288 KB Output is correct
7 Correct 2647 ms 166808 KB Output is correct
8 Correct 2679 ms 168108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 601 ms 116316 KB Output is correct
6 Correct 1455 ms 135616 KB Output is correct
7 Correct 2170 ms 152228 KB Output is correct
8 Correct 2739 ms 170800 KB Output is correct
9 Correct 253 ms 15968 KB Output is correct
10 Correct 258 ms 17500 KB Output is correct
11 Correct 289 ms 17864 KB Output is correct
12 Correct 2888 ms 169616 KB Output is correct
13 Correct 2699 ms 170956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 2992 ms 172412 KB Output is correct
6 Correct 2469 ms 157492 KB Output is correct
7 Correct 1578 ms 141292 KB Output is correct
8 Correct 656 ms 116360 KB Output is correct
9 Correct 371 ms 12080 KB Output is correct
10 Correct 245 ms 7180 KB Output is correct
11 Correct 369 ms 12140 KB Output is correct
12 Correct 243 ms 7160 KB Output is correct
13 Correct 374 ms 12016 KB Output is correct
14 Correct 244 ms 7128 KB Output is correct
15 Correct 2713 ms 169184 KB Output is correct
16 Correct 2709 ms 170544 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 261 ms 14304 KB Output is correct
9 Correct 326 ms 15896 KB Output is correct
10 Correct 616 ms 22224 KB Output is correct
11 Correct 2009 ms 147376 KB Output is correct
12 Correct 2177 ms 151216 KB Output is correct
13 Correct 1582 ms 140288 KB Output is correct
14 Correct 2647 ms 166808 KB Output is correct
15 Correct 2679 ms 168108 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 4 ms 760 KB Output is correct
18 Correct 4 ms 760 KB Output is correct
19 Correct 5 ms 760 KB Output is correct
20 Correct 601 ms 116316 KB Output is correct
21 Correct 1455 ms 135616 KB Output is correct
22 Correct 2170 ms 152228 KB Output is correct
23 Correct 2739 ms 170800 KB Output is correct
24 Correct 253 ms 15968 KB Output is correct
25 Correct 258 ms 17500 KB Output is correct
26 Correct 289 ms 17864 KB Output is correct
27 Correct 2888 ms 169616 KB Output is correct
28 Correct 2699 ms 170956 KB Output is correct
29 Correct 5 ms 760 KB Output is correct
30 Correct 4 ms 760 KB Output is correct
31 Correct 4 ms 760 KB Output is correct
32 Correct 3 ms 636 KB Output is correct
33 Correct 2992 ms 172412 KB Output is correct
34 Correct 2469 ms 157492 KB Output is correct
35 Correct 1578 ms 141292 KB Output is correct
36 Correct 656 ms 116360 KB Output is correct
37 Correct 371 ms 12080 KB Output is correct
38 Correct 245 ms 7180 KB Output is correct
39 Correct 369 ms 12140 KB Output is correct
40 Correct 243 ms 7160 KB Output is correct
41 Correct 374 ms 12016 KB Output is correct
42 Correct 244 ms 7128 KB Output is correct
43 Correct 2713 ms 169184 KB Output is correct
44 Correct 2709 ms 170544 KB Output is correct
45 Correct 116 ms 7456 KB Output is correct
46 Correct 228 ms 8840 KB Output is correct
47 Correct 1029 ms 58984 KB Output is correct
48 Correct 1887 ms 146740 KB Output is correct
49 Correct 308 ms 19856 KB Output is correct
50 Correct 298 ms 19676 KB Output is correct
51 Correct 331 ms 20148 KB Output is correct
52 Correct 425 ms 23988 KB Output is correct
53 Correct 427 ms 24060 KB Output is correct
54 Correct 428 ms 23896 KB Output is correct