oj.uz

Submission #1113331

# Submission time Handle Problem Language Result Execution time Memory
1113331 2024-11-16T11:46:02 Z julia_08 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 50 ms 3408 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 3400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 848 KB Output is correct
2 Correct 9 ms 1360 KB Output is correct
3 Correct 12 ms 1360 KB Output is correct
4 Correct 33 ms 1896 KB Output is correct
5 Correct 42 ms 3144 KB Output is correct
6 Correct 39 ms 3156 KB Output is correct
7 Correct 35 ms 3408 KB Output is correct
8 Correct 39 ms 3160 KB Output is correct
9 Correct 40 ms 3188 KB Output is correct
10 Correct 38 ms 3144 KB Output is correct
11 Correct 36 ms 3144 KB Output is correct
12 Correct 37 ms 3144 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 2888 KB Output isn't correct
2 Halted 0 ms 0 KB -