Submission #774483

#	Time	Username	Problem	Language	Result	Execution time	Memory
774483		m_bezrutchka	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	172 ms	7708 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75