oj.uz

Submission #551301

# Submission time Handle Problem Language Result Execution time Memory
551301 2022-04-20T08:41:45 Z Soumya1 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2405 ms 165612 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 3e5 + 2;
vector<int> t[4 * mxN], kk[mxN];
int sz[4 * mxN];
pair<int, int> bit[mxN * 30];
int ii;
vector<tuple<int, int, int, int>> g;
struct BIT {
  int n;
  int s;
  BIT() { }
  BIT(int _n) {
    n = _n;
    s = ii;
    ii += n;
  }
  void add(int i, int a, int b) {
    for (; i <= n; i = i | (i + 1)) bit[i + s].first += a, bit[i + s].second += b;
  }
  pair<int, int> sum(int r) {
    pair<int, int> ret = {0, 0};
    for (; r >= 1; r = (r & (r + 1)) - 1) {
      ret.first += bit[r + s].first;
      ret.second += bit[r + s].second;
    }
    return ret;
  }
  pair<int, int> sum(int l, int r) {
    auto a = sum(r);
    auto b = sum(l - 1);
    return {a.first - b.first, a.second - b.second};
  }
} bb[4 * mxN];
void build(int x, int lx, int rx) {
  if (lx == rx) {
    t[x] = kk[lx];
    t[x].push_back(1e9);
    sort(t[x].begin(), t[x].end());
    t[x].erase(unique(t[x].begin(), t[x].end()), t[x].end());
    sz[x] = t[x].size();
    bb[x] = BIT(sz[x]);
    return;
  }
  int mx = (lx + rx) >> 1;
  build(x << 1, lx, mx);
  build(x << 1 | 1, mx + 1, rx);
  merge(t[x << 1].begin(), t[x << 1].end(), t[x << 1 | 1].begin(), t[x << 1 | 1].end(), back_inserter(t[x]));
  t[x].erase(unique(t[x].begin(), t[x].end()), t[x].end());
  sz[x] = t[x].size();
  bb[x] = BIT(sz[x]);
}
void update(int x, int lx, int rx, int i, int y, int timer, int tt) {
  if (lx == rx) {
    int yy = lower_bound(t[x].begin(), t[x].end(), y) - t[x].begin() + 1;
    bb[x].add(yy, timer, tt);
    return;
  }
  int mx = (lx + rx) >> 1;
  if (i <= mx) update(x << 1, lx, mx, i, y, timer, tt);
  else update(x << 1 | 1, mx + 1, rx, i, y, timer, tt);
  int yy = lower_bound(t[x].begin(), t[x].end(), y) - t[x].begin() + 1;
  bb[x].add(yy, timer, tt);
}
pair<int, int> query(int x, int lx, int rx, int l, int r, int y) {
  if (lx > r || l > rx) return {0, 0};
  if (l <= lx && r >= rx) {
    int yy = lower_bound(t[x].begin(), t[x].end(), y) - t[x].begin();
    return bb[x].sum(yy + 1, sz[x]);
  }
  int mx = (lx + rx) >> 1;
  auto a = query(x << 1, lx, mx, l, r, y);
  auto b = query(x << 1 | 1, mx + 1, rx, l, r, y);
  return {a.first + b.first, a.second + b.second};
}
void testCase() {
  int n, q;
  cin >> n >> q;
  {
    string s;
    cin >> s;
    s = '0' + s;
    s += '0';
    int l = -1;
    set<pair<int, int>> st;
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1' && s[i - 1] != '1') l = i;
      if (s[i] == '1' && s[i + 1] != '1') {
        g.push_back({0, 1, l, i + 1});
        st.insert({l, i + 1});
      }
    }
    for (int time = 1; time <= q; time++) {
      string t;
      cin >> t;
      if (t[0] == 'q') {
        int a, b;
        cin >> a >> b;
        g.push_back({time, 3, a, b});
      } else {
        int i;
        cin >> i;
        if (s[i] == '1') {
          auto p = *prev(st.upper_bound({i, 1e9}));
          st.erase(p);
          g.push_back({time, 2, p.first, p.second});
          if (s[i - 1] == '1') {
            g.push_back({time, 1, p.first, i});
            st.insert({p.first, i});
          }
          if (s[i + 1] == '1') {
            g.push_back({time, 1, i + 1, p.second});
            st.insert({i + 1, p.second});
          }
          s[i] = '0';
        } else {
          if (s[i + 1] == '1' && s[i - 1] == '1') {
            auto p = *st.upper_bound({i, 0});
            g.push_back({time, 2, p.first, p.second});
            st.erase(p);
            auto pp = *prev(st.upper_bound({i, 0}));
            st.erase(pp);
            g.push_back({time, 2, pp.first, pp.second});
            st.insert({pp.first, p.second});
            g.push_back({time, 1, pp.first, p.second});
          } else if (s[i + 1] == '1') {
            auto p = *st.upper_bound({i, 0});
            st.erase(p);
            g.push_back({time, 2, p.first, p.second});
            st.insert({i, p.second});
            g.push_back({time, 1, i, p.second});
          } else if (s[i - 1] == '1') {
            auto p = *prev(st.lower_bound({i, 0}));
            st.erase(p);
            g.push_back({time, 2, p.first, p.second});
            st.insert({p.first, i + 1});
            g.push_back({time, 1, p.first, i + 1});
          } else {
            g.push_back({time, 1, i, i + 1});
            st.insert({i, i + 1});
          }
          s[i] = '1';
        }
      }
    }
  }
  sort(g.begin(), g.end());
  for (auto [a, b, c, d] : g) {
    kk[c].push_back(d);
  }
  build(1, 1, n);
  for (auto [a, b, c, d] : g) {
    if (b == 1) {
      update(1, 1, n, c, d, -a, 1);
    } else if (b == 2) {
      update(1, 1, n, c, d, a, -1);
    } else {
      auto x = query(1, 1, n, 1, c, d);
      cout << 1LL * a * x.second + x.first << "\n";
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35540 KB Output is correct
2 Correct 17 ms 35540 KB Output is correct
3 Correct 19 ms 35548 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 19 ms 35556 KB Output is correct
6 Correct 19 ms 35512 KB Output is correct
7 Correct 19 ms 35540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 51712 KB Output is correct
2 Correct 318 ms 52832 KB Output is correct
3 Correct 526 ms 55820 KB Output is correct
4 Correct 1760 ms 143352 KB Output is correct
5 Correct 1751 ms 146156 KB Output is correct
6 Correct 1772 ms 143324 KB Output is correct
7 Correct 751 ms 100200 KB Output is correct
8 Correct 688 ms 101680 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35796 KB Output is correct
2 Correct 21 ms 35828 KB Output is correct
3 Correct 20 ms 35788 KB Output is correct
4 Correct 19 ms 35668 KB Output is correct
5 Correct 2306 ms 137904 KB Output is correct
6 Correct 2248 ms 153972 KB Output is correct
7 Correct 2132 ms 158164 KB Output is correct
8 Correct 1004 ms 110876 KB Output is correct
9 Correct 138 ms 45684 KB Output is correct
10 Correct 148 ms 46872 KB Output is correct
11 Correct 161 ms 47036 KB Output is correct
12 Correct 1010 ms 109516 KB Output is correct
13 Correct 1020 ms 110952 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35924 KB Output is correct
2 Correct 20 ms 35780 KB Output is correct
3 Correct 20 ms 35796 KB Output is correct
4 Correct 22 ms 35824 KB Output is correct
5 Correct 1363 ms 165612 KB Output is correct
6 Correct 1604 ms 159872 KB Output is correct
7 Correct 1954 ms 155136 KB Output is correct
8 Correct 2405 ms 142544 KB Output is correct
9 Correct 400 ms 56300 KB Output is correct
10 Correct 323 ms 54804 KB Output is correct
11 Correct 388 ms 56272 KB Output is correct
12 Correct 324 ms 54848 KB Output is correct
13 Correct 407 ms 56400 KB Output is correct
14 Correct 317 ms 54796 KB Output is correct
15 Correct 1004 ms 109352 KB Output is correct
16 Correct 1032 ms 110792 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35540 KB Output is correct
2 Correct 17 ms 35540 KB Output is correct
3 Correct 19 ms 35548 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 19 ms 35556 KB Output is correct
6 Correct 19 ms 35512 KB Output is correct
7 Correct 19 ms 35540 KB Output is correct
8 Correct 255 ms 51712 KB Output is correct
9 Correct 318 ms 52832 KB Output is correct
10 Correct 526 ms 55820 KB Output is correct
11 Correct 1760 ms 143352 KB Output is correct
12 Correct 1751 ms 146156 KB Output is correct
13 Correct 1772 ms 143324 KB Output is correct
14 Correct 751 ms 100200 KB Output is correct
15 Correct 688 ms 101680 KB Output is correct
16 Correct 23 ms 35796 KB Output is correct
17 Correct 21 ms 35828 KB Output is correct
18 Correct 20 ms 35788 KB Output is correct
19 Correct 19 ms 35668 KB Output is correct
20 Correct 2306 ms 137904 KB Output is correct
21 Correct 2248 ms 153972 KB Output is correct
22 Correct 2132 ms 158164 KB Output is correct
23 Correct 1004 ms 110876 KB Output is correct
24 Correct 138 ms 45684 KB Output is correct
25 Correct 148 ms 46872 KB Output is correct
26 Correct 161 ms 47036 KB Output is correct
27 Correct 1010 ms 109516 KB Output is correct
28 Correct 1020 ms 110952 KB Output is correct
29 Correct 20 ms 35924 KB Output is correct
30 Correct 20 ms 35780 KB Output is correct
31 Correct 20 ms 35796 KB Output is correct
32 Correct 22 ms 35824 KB Output is correct
33 Correct 1363 ms 165612 KB Output is correct
34 Correct 1604 ms 159872 KB Output is correct
35 Correct 1954 ms 155136 KB Output is correct
36 Correct 2405 ms 142544 KB Output is correct
37 Correct 400 ms 56300 KB Output is correct
38 Correct 323 ms 54804 KB Output is correct
39 Correct 388 ms 56272 KB Output is correct
40 Correct 324 ms 54848 KB Output is correct
41 Correct 407 ms 56400 KB Output is correct
42 Correct 317 ms 54796 KB Output is correct
43 Correct 1004 ms 109352 KB Output is correct
44 Correct 1032 ms 110792 KB Output is correct
45 Correct 112 ms 45720 KB Output is correct
46 Correct 188 ms 45972 KB Output is correct
47 Correct 962 ms 91024 KB Output is correct
48 Correct 1943 ms 157352 KB Output is correct
49 Correct 171 ms 47564 KB Output is correct
50 Correct 165 ms 47440 KB Output is correct
51 Correct 172 ms 47944 KB Output is correct
52 Correct 224 ms 51628 KB Output is correct
53 Correct 248 ms 51356 KB Output is correct
54 Correct 197 ms 51408 KB Output is correct