Submission #548261

#	Time	Username	Problem	Language	Result	Execution time	Memory
548261		Alex_tz307	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	206 ms	5300 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75