oj.uz

Submission #548261

# Submission time Handle Problem Language Result Execution time Memory
548261 2022-04-12T20:16:47 Z Alex_tz307 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 206 ms 5300 KB 
#include <bits/stdc++.h>

using namespace std;

struct ST {
  int n;
  vector<int64_t> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      cin >> t[x];
      return;
    }
    int mid = (lx + rx) / 2;
    build(x * 2, lx, mid);
    build(x * 2 + 1, mid + 1, rx);
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void setPos(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      t[x] = v;
      return;
    }
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      setPos(x * 2, lx, mid, pos, v);
    } else {
      setPos(x * 2 + 1, mid + 1, rx, pos, v);
    }
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void setPos(int pos, int v) {
    setPos(1, 1, n, pos, v);
  }

  void update(int x, int lx, int rx, int st, int dr, int k) {
    if (t[x] == 0) {
      return;
    }
    if (lx == rx) {
      t[x] /= k;
      return;
    }
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      update(x * 2, lx, mid, st, dr, k);
    }
    if (mid < dr) {
      update(x * 2 + 1, mid + 1, rx, st, dr, k);
    }
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void update(int st, int dr, int k) {
    if (k == 1) {
      return;
    }
    update(1, 1, n, st, dr, k);
  }

  int64_t query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }
    int mid = (lx + rx) / 2;
    int64_t ans = 0;
    if (st <= mid) {
      ans += query(x * 2, lx, mid, st, dr);
    }
    if (mid < dr) {
      ans += query(x * 2 + 1, mid + 1, rx, st, dr);
    }
    return ans;
  }

  int64_t query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

void testCase() {
  int n, q, k;
  cin >> n >> q >> k;
  ST t(n);
  t.build(1, 1, n);
  for (int i = 0; i < q; ++i) {
    char op;
    int x, y;
    cin >> op >> x >> y;
    if (op == '1') {
      t.setPos(x, y);
    } else if (op == '2') {
      t.update(x, y, k);
    } else {
      cout << t.query(x, y) << '\n';
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3660 KB Output is correct
2 Correct 35 ms 3456 KB Output is correct
3 Correct 31 ms 4288 KB Output is correct
4 Correct 43 ms 4800 KB Output is correct
5 Correct 49 ms 5196 KB Output is correct
6 Correct 51 ms 5296 KB Output is correct
7 Correct 56 ms 5300 KB Output is correct
8 Correct 48 ms 5268 KB Output is correct
9 Correct 45 ms 5092 KB Output is correct
10 Correct 51 ms 5128 KB Output is correct
11 Correct 52 ms 5132 KB Output is correct
12 Correct 55 ms 5156 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 832 KB Output is correct
2 Correct 10 ms 1620 KB Output is correct
3 Correct 15 ms 1776 KB Output is correct
4 Correct 39 ms 2008 KB Output is correct
5 Correct 46 ms 3788 KB Output is correct
6 Correct 50 ms 3780 KB Output is correct
7 Correct 47 ms 3968 KB Output is correct
8 Correct 47 ms 3784 KB Output is correct
9 Correct 59 ms 3652 KB Output is correct
10 Correct 48 ms 3676 KB Output is correct
11 Correct 43 ms 3660 KB Output is correct
12 Correct 45 ms 3668 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3024 KB Output is correct
2 Correct 71 ms 3148 KB Output is correct
3 Correct 94 ms 2664 KB Output is correct
4 Correct 102 ms 2796 KB Output is correct
5 Correct 118 ms 5104 KB Output is correct
6 Correct 122 ms 5108 KB Output is correct
7 Correct 114 ms 5128 KB Output is correct
8 Correct 159 ms 5096 KB Output is correct
9 Correct 141 ms 4968 KB Output is correct
10 Correct 164 ms 4928 KB Output is correct
11 Correct 121 ms 4928 KB Output is correct
12 Correct 206 ms 5012 KB Output is correct