oj.uz

Submission #774483

# Submission time Handle Problem Language Result Execution time Memory
774483 2023-07-05T18:39:58 Z m_bezrutchka Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 172 ms 7708 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[4 * 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 1 ms 212 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 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2964 KB Output is correct
2 Correct 37 ms 4444 KB Output is correct
3 Correct 31 ms 6608 KB Output is correct
4 Correct 39 ms 7200 KB Output is correct
5 Correct 47 ms 7704 KB Output is correct
6 Correct 47 ms 7708 KB Output is correct
7 Correct 46 ms 7648 KB Output is correct
8 Correct 46 ms 7628 KB Output is correct
9 Correct 44 ms 7568 KB Output is correct
10 Correct 44 ms 7580 KB Output is correct
11 Correct 45 ms 7568 KB Output is correct
12 Correct 45 ms 7472 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 596 KB Output is correct
2 Correct 11 ms 2536 KB Output is correct
3 Correct 14 ms 2900 KB Output is correct
4 Correct 41 ms 2572 KB Output is correct
5 Correct 48 ms 6200 KB Output is correct
6 Correct 49 ms 6256 KB Output is correct
7 Correct 47 ms 6284 KB Output is correct
8 Correct 48 ms 6220 KB Output is correct
9 Correct 45 ms 6044 KB Output is correct
10 Correct 45 ms 6052 KB Output is correct
11 Correct 47 ms 6068 KB Output is correct
12 Correct 44 ms 6100 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2620 KB Output is correct
2 Correct 66 ms 4340 KB Output is correct
3 Correct 73 ms 3784 KB Output is correct
4 Correct 86 ms 3292 KB Output is correct
5 Correct 98 ms 7404 KB Output is correct
6 Correct 107 ms 7456 KB Output is correct
7 Correct 105 ms 7416 KB Output is correct
8 Correct 129 ms 7484 KB Output is correct
9 Correct 129 ms 7292 KB Output is correct
10 Correct 137 ms 7392 KB Output is correct
11 Correct 97 ms 7276 KB Output is correct
12 Correct 172 ms 7368 KB Output is correct