oj.uz

Submission #132491

# Submission time Handle Problem Language Result Execution time Memory
132491 2019-07-19T04:26:06 Z Just_Solve_The_Problem Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 305 ms 6904 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 20 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3196 KB Output is correct
2 Correct 63 ms 4060 KB Output is correct
3 Correct 60 ms 5660 KB Output is correct
4 Correct 74 ms 6264 KB Output is correct
5 Correct 90 ms 6748 KB Output is correct
6 Correct 92 ms 6776 KB Output is correct
7 Correct 92 ms 6776 KB Output is correct
8 Correct 92 ms 6904 KB Output is correct
9 Correct 80 ms 6648 KB Output is correct
10 Correct 81 ms 6520 KB Output is correct
11 Correct 85 ms 6660 KB Output is correct
12 Correct 81 ms 6636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 632 KB Output is correct
2 Correct 18 ms 2172 KB Output is correct
3 Correct 24 ms 2168 KB Output is correct
4 Correct 63 ms 1400 KB Output is correct
5 Correct 84 ms 4008 KB Output is correct
6 Correct 85 ms 3960 KB Output is correct
7 Correct 76 ms 4776 KB Output is correct
8 Correct 83 ms 5240 KB Output is correct
9 Correct 79 ms 5084 KB Output is correct
10 Correct 73 ms 5112 KB Output is correct
11 Correct 78 ms 5296 KB Output is correct
12 Correct 74 ms 5240 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2380 KB Output is correct
2 Correct 115 ms 2424 KB Output is correct
3 Correct 140 ms 2424 KB Output is correct
4 Correct 149 ms 1656 KB Output is correct
5 Correct 172 ms 4292 KB Output is correct
6 Correct 192 ms 4216 KB Output is correct
7 Correct 166 ms 4168 KB Output is correct
8 Correct 231 ms 4220 KB Output is correct
9 Correct 192 ms 4216 KB Output is correct
10 Correct 219 ms 4376 KB Output is correct
11 Correct 165 ms 4216 KB Output is correct
12 Correct 305 ms 4316 KB Output is correct