Submission #1115505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115505		Skymagic	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	138 ms	5976 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
struct node{
  ll 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;
}
 
ll 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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75