oj.uz

Submission #599703

# Submission time Handle Problem Language Result Execution time Memory
599703 2022-07-19T19:15:07 Z MilosMilutinovic Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2335 ms 430548 KB 
/**
 *    author:  wxhtzdy
 *    created: 19.07.2022 20:06:36
**/
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 3e5 + 5;
const int M = 120 * N; 

int root[N], ls[M], rs[M], tsz;
long long st[M];

void modify(int& c, int l, int r, int ll, int rr, int v) {
  if (!c) {
    c = ++tsz;
  }
  if (l > r || ll > rr || l > rr || r < ll) {
    return;
  }
  if (ll <= l && r <= rr) {
    st[c] += v;
    return;
  }
  int mid = l + r >> 1;
  modify(ls[c], l, mid, ll, rr, v);
  modify(rs[c], mid + 1, r, ll, rr, v);      
}

void modify(int x, int l, int r, int v) {
  for (x++; x < N; x += x & -x) {
    modify(root[x], 0, N - 1, l, r, v);
  }
}

void modify(int l, int r, int ll, int rr, int v) {
  modify(l, ll, rr, v);
  modify(r + 1, ll, rr, -v);
}

long long get(int c, int l, int r, int i) {
  if (!c) {
    return 0;
  }
  if (l == r) {
    return st[c];
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    return st[c] + get(ls[c], l, mid, i);
  } else {
    return st[c] + get(rs[c], mid + 1, r, i);
  }
}

int get(int x, int y) {
  long long res = 0;
  for (x++; x > 0; x -= x & -x) {
    res += get(root[x], 0, N - 1, y);
  }
  return res;
}  

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<pair<int, int>> segs;
  vector<bool> on(N);
  auto Add = [&](int i, int t) {
    pair<int, int> new_seg = {i, i}; 
    {
      auto it = segs.lower_bound({i + 1, -1});
      if (it != segs.begin()) {
        --it;
        auto p = *it;
        if (p.second == i - 1) {
          segs.erase(it);
          new_seg.first = p.first;
        }
      }
    }
    {
      auto it = segs.lower_bound({i + 1, -1});
      if (it != segs.end()) {
        auto p = *it;
        if (p.first == i + 1) {
          segs.erase(it);
          new_seg.second = p.second;
        }
      }
    }
    modify(new_seg.first, i, i, new_seg.second, -t);
    segs.emplace(new_seg);
    on[i] = true;
  };
  auto Remove = [&](int i, int t) {
    auto it = prev(segs.lower_bound({i + 1, -1}));
    auto p = *it;
    modify(p.first, i, i, p.second, +t);
    segs.erase(it);
    if (p.first < i) {
      segs.emplace(p.first, i - 1);
    }
    if (i < p.second) {
      segs.emplace(i + 1, p.second);
    }
    on[i] = false;
  };      
  for (int i = 0; i < n; i++) {
    if (s[i] == '1') {
      Add(i, 0);
    }
  } 
  for (int t = 1; t <= q; t++) {
    string op;
    cin >> op;
    if (op == "toggle") {
      int i;
      cin >> i;
      --i;     
      if (!on[i]) {
        Add(i, t);
      } else {
        Remove(i, t);
      }
    } else {
      int l, r;
      cin >> l >> r;
      --l; --r;
      int ans = get(l, r - 1);
      auto it = segs.lower_bound({l + 1, -1});
      if (it != segs.begin()) {
        --it;
        if (it->first <= l && it->second >= r - 1) {
          ans += t;
        }
      } 
      cout << ans << '\n';
    }
  }
  return 0;
}

Compilation message

street_lamps.cpp: In function 'void modify(int&, int, int, int, int, int)':
street_lamps.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'long long int get(int, int, int, int)':
street_lamps.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 1396 KB Output is correct
2 Correct 673 ms 1896 KB Output is correct
3 Correct 814 ms 7328 KB Output is correct
4 Correct 2013 ms 260284 KB Output is correct
5 Correct 2086 ms 296988 KB Output is correct
6 Correct 2123 ms 268988 KB Output is correct
7 Correct 109 ms 7260 KB Output is correct
8 Correct 2299 ms 430436 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1492 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 5 ms 1492 KB Output is correct
4 Correct 6 ms 1620 KB Output is correct
5 Correct 2178 ms 296148 KB Output is correct
6 Correct 1997 ms 301108 KB Output is correct
7 Correct 1797 ms 301568 KB Output is correct
8 Correct 1871 ms 430548 KB Output is correct
9 Correct 88 ms 4108 KB Output is correct
10 Correct 103 ms 4472 KB Output is correct
11 Correct 94 ms 4704 KB Output is correct
12 Correct 103 ms 7236 KB Output is correct
13 Correct 1784 ms 430468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 4 ms 1388 KB Output is correct
3 Correct 5 ms 1328 KB Output is correct
4 Correct 7 ms 1364 KB Output is correct
5 Correct 944 ms 227716 KB Output is correct
6 Correct 1278 ms 250376 KB Output is correct
7 Correct 1698 ms 263464 KB Output is correct
8 Correct 2335 ms 273480 KB Output is correct
9 Correct 855 ms 1112 KB Output is correct
10 Correct 1129 ms 672 KB Output is correct
11 Correct 858 ms 1108 KB Output is correct
12 Correct 1124 ms 564 KB Output is correct
13 Correct 853 ms 1104 KB Output is correct
14 Correct 1119 ms 664 KB Output is correct
15 Correct 99 ms 1240 KB Output is correct
16 Correct 1727 ms 430500 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 669 ms 1396 KB Output is correct
9 Correct 673 ms 1896 KB Output is correct
10 Correct 814 ms 7328 KB Output is correct
11 Correct 2013 ms 260284 KB Output is correct
12 Correct 2086 ms 296988 KB Output is correct
13 Correct 2123 ms 268988 KB Output is correct
14 Correct 109 ms 7260 KB Output is correct
15 Correct 2299 ms 430436 KB Output is correct
16 Correct 6 ms 1492 KB Output is correct
17 Correct 5 ms 1492 KB Output is correct
18 Correct 5 ms 1492 KB Output is correct
19 Correct 6 ms 1620 KB Output is correct
20 Correct 2178 ms 296148 KB Output is correct
21 Correct 1997 ms 301108 KB Output is correct
22 Correct 1797 ms 301568 KB Output is correct
23 Correct 1871 ms 430548 KB Output is correct
24 Correct 88 ms 4108 KB Output is correct
25 Correct 103 ms 4472 KB Output is correct
26 Correct 94 ms 4704 KB Output is correct
27 Correct 103 ms 7236 KB Output is correct
28 Correct 1784 ms 430468 KB Output is correct
29 Correct 3 ms 1236 KB Output is correct
30 Correct 4 ms 1388 KB Output is correct
31 Correct 5 ms 1328 KB Output is correct
32 Correct 7 ms 1364 KB Output is correct
33 Correct 944 ms 227716 KB Output is correct
34 Correct 1278 ms 250376 KB Output is correct
35 Correct 1698 ms 263464 KB Output is correct
36 Correct 2335 ms 273480 KB Output is correct
37 Correct 855 ms 1112 KB Output is correct
38 Correct 1129 ms 672 KB Output is correct
39 Correct 858 ms 1108 KB Output is correct
40 Correct 1124 ms 564 KB Output is correct
41 Correct 853 ms 1104 KB Output is correct
42 Correct 1119 ms 664 KB Output is correct
43 Correct 99 ms 1240 KB Output is correct
44 Correct 1727 ms 430500 KB Output is correct
45 Correct 435 ms 2728 KB Output is correct
46 Correct 449 ms 2892 KB Output is correct
47 Correct 850 ms 98172 KB Output is correct
48 Correct 1768 ms 265020 KB Output is correct
49 Correct 115 ms 4608 KB Output is correct
50 Correct 112 ms 4540 KB Output is correct
51 Correct 107 ms 4788 KB Output is correct
52 Correct 113 ms 5528 KB Output is correct
53 Correct 104 ms 5184 KB Output is correct
54 Correct 120 ms 5404 KB Output is correct