oj.uz

Submission #774482

# Submission time Handle Problem Language Result Execution time Memory
774482 2023-07-05T18:38:17 Z m_bezrutchka Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 64 ms 4748 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 112345;
int n, K;
int v[MAXN];

struct seg {
  ll sum;
  int max_val;
  seg () {}
  seg(ll a, int b) {
    sum = a; max_val = b;
  }
};

seg node[MAXN];

void build(int i, int l, int r) {
  if (l == r) {
    node[i] = seg((ll) v[l], v[l]);
    return;
  }
  int m = (l + r) / 2;
  build(2 * i, l, m);
  build(2 * i + 1, m + 1, r);
  node[i].sum = node[2 * i].sum + node[2 * i + 1].sum;
  node[i].max_val = max(node[2 * i].max_val, node[2 * i + 1].max_val);
}

void set(int i, int l, int r, int pos, int val) {
  if (l == r) {
    v[pos] = val;
    node[i] = seg((ll) v[pos], v[pos]);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    set(2 * i, l, m, pos, val);
  } else {
    set(2 * i + 1, m + 1, r, pos, val);
  }
  node[i].sum = node[2 * i].sum + node[2 * i + 1].sum;
  node[i].max_val = max(node[2 * i].max_val, node[2 * i + 1].max_val);
}

void spray(int i, int l, int r, int a, int b) {
  if (b < l || a > r || node[i].max_val == 0) {
    return;
  }
  if (l == r) {
    v[l] /= K;
    node[i] = seg((ll) v[l], v[l]);
    return;
  }
  int m = (l + r) / 2;
  spray(2 * i, l, m, a, b);
  spray(2 * i + 1, m + 1, r, a, b);
  node[i].sum = node[2 * i].sum + node[2 * i + 1].sum;
  node[i].max_val = max(node[2 * i].max_val, node[2 * i + 1].max_val);
}

ll query(int i, int l, int r, int a, int b) {
  if (b < l || a > r) return 0LL;
  if (a <= l && r <= b) return node[i].sum;
  int m = (l + r) / 2;
  return query(2 * i, l, m, a, b) + query(2 * i + 1, m + 1, r, a, b);
}

void print_seg(int i, int l, int r) {
  printf("node(%d) [%d %d]: sum = %lld, max = %d\n", i, l, r, node[i].sum, node[i].max_val);
  if (l == r) {
    return;
  }
  int m = (l + r) / 2;
  print_seg(2 * i, l, m);
  print_seg(2 * i + 1, m + 1, r);
}

int main() {
  int q, s, t, u;
  scanf("%d %d %d", &n, &q, &K);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
  }
  build(1, 1, n);
  for (int i = 1; i <= q; i++) {
    // print_seg(1, 1, n);
    scanf("%d %d %d", &s, &t, &u);
    if (s == 1) {
      set(1, 1, n, t, u);
    } else if (s == 2) {
      if (K > 1) {
        spray(1, 1, n, t, u);
      }
    } else {
      printf("%lld\n", query(1, 1, n, t, u));
    }
  }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d %d %d", &n, &q, &K);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d %d %d", &s, &t, &u);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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 352 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 432 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 3 ms 496 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 3 ms 492 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 960 KB Output is correct
2 Incorrect 10 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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