Submission #132491

#	Time	Username	Problem	Language	Result	Execution time	Memory
132491		Just_Solve_The_Problem	Sterilizing Spray (JOI15_sterilizing)	C++11	100 / 100	305 ms	6904 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = (int)1e5 + 7;

int a[N];
int n, q, k;

struct T {
  ll tree[4 * N];
  int mx[4 * N];
  T() {}
  void build(int v = 1, int l = 1, int r = n) {
    if (l == r) {
      tree[v] = mx[v] = a[l];
      return ;
    }
    int mid = (l + r) >> 1;
    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
    tree[v] = tree[v + v] + tree[v + v + 1];
    mx[v] = max(mx[v + v], mx[v + v + 1]);
  }
  void upd(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (tl > r || tr < l || mx[v] == 0) return ;
    if (tl == tr) {
      tree[v] /= k;
      mx[v] /= k;
      return ;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, v + v, tl, mid);
    upd(l, r, v + v + 1, mid + 1, tr);
    tree[v] = tree[v + v] + tree[v + v + 1];
    mx[v] = max(mx[v + v], mx[v + v + 1]);
  }
  void updpos(int pos, int val, int v = 1, int tl = 1, int tr = n) {
    if (tl == tr) {
      tree[v] = mx[v] = val;
      return ;
    }
    int mid = (tl + tr) >> 1;
    if (pos <= mid) {
      updpos(pos, val, v + v, tl, mid);
    } else {
      updpos(pos, val, v + v + 1, mid + 1, tr);
    }
    tree[v] = tree[v + v] + tree[v + v + 1];
    mx[v] = max(mx[v + v], mx[v + v + 1]);
  }
  ll get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (tl > r || tr < l) return 0;
    if (l <= tl && tr <= r) return tree[v];
    int mid = (tl + tr) >> 1;
    return get(l, r, v + v, tl, mid) + get(l, r, v + v + 1, mid + 1, tr);
  }
};
T tr;

main() {
  scanf("%d %d %d", &n, &q, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  tr.build();
  while (q--) {
    int s, t, u;
    scanf("%d %d %d", &s, &t, &u);
    if (s == 1) {
      tr.updpos(t, u);
    } else if (s == 2) {
      if (k == 1) continue;
      tr.upd(t, u);
    } else {
      printf("%lld\n", tr.get(t, u));
    }
  }
}

Compilation message (stderr)

sterilizing.cpp:63:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &n, &q, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &s, &t, &u);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75