Submission #1113331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113331		julia_08	Sterilizing Spray (JOI15_sterilizing)	C++17	10 / 100	50 ms	3408 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

struct node{
  int sum;
};

const int MAXN = 1e5 + 10;

int a[MAXN];

node seg[4 * MAXN];

void build(int x, int lx, int rx){

  if(lx == rx){
    seg[x].sum = a[lx];
    return;
  }

  int m = (lx + rx) / 2;

  int lc = 2 * x, rc = 2 * x + 1;

  build(lc, lx, m);
  build(rc, m + 1, rx);

  seg[x].sum = seg[lc].sum + seg[rc].sum;
}

void update_set(int x, int lx, int rx, int i, int val){

  if(rx < i || lx > i) return;

  if(lx == rx){
    seg[x].sum = val;

    return;
  }

  int m = (lx + rx) / 2;

  int lc = 2 * x, rc = 2 * x + 1;

  update_set(lc, lx, m, i, val);
  update_set(rc, m + 1, rx, i, val);

  seg[x].sum = seg[lc].sum + seg[rc].sum;
}

void update(int x, int lx, int rx, int l, int r, int k){

  if(rx < l || lx > r || seg[x].sum == 0) return;

  if(lx == rx){
    seg[x].sum /= k;
    return;
  }

  int m = (lx + rx) / 2;

  int lc = 2 * x, rc = 2 * x + 1;

  update(lc, lx, m, l, r, k);
  update(rc, m + 1, rx, l, r, k);

  seg[x].sum = seg[lc].sum + seg[rc].sum;
}

int query(int x, int lx, int rx, int l, int r){

  if(rx < l || lx > r) return 0;

  if(l <= lx && rx <= r) return seg[x].sum;

  int m = (lx + rx) / 2;

  int lc = 2 * x, rc = 2 * x + 1;

  return query(lc, lx, m, l, r) + query(rc, m + 1, rx, l, r);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, q, k; cin >> n >> q >> k;

  for(int i=1; i<=n; i++){
    cin >> a[i];
  }

  build(1, 1, n);

  while(q--){

    int t, a, b; cin >> t >> a >> b;

    if(t == 1){
      update_set(1, 1, n, a, b);

    } else if(t == 2){
      if(k != 1) update(1, 1, n, a, b, k);

    } else{
      cout << query(1, 1, n, a, b) << "\n";

    }

  }

  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75