oj.uz

Submission #132489

# Submission time Handle Problem Language Result Execution time Memory
132489 2019-07-19T04:23:40 Z Just_Solve_The_Problem Sterilizing Spray (JOI15_sterilizing) C++11
75 / 100
 5000 ms 6648 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) {
      if (k == 1) continue;
      tr.updpos(t, u);
    } else if (s == 2) {
      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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5063 ms 4140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1016 KB Output is correct
2 Correct 19 ms 2296 KB Output is correct
3 Correct 25 ms 2424 KB Output is correct
4 Correct 64 ms 2424 KB Output is correct
5 Correct 85 ms 5284 KB Output is correct
6 Correct 85 ms 5240 KB Output is correct
7 Execution timed out 5090 ms 4892 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 3836 KB Output is correct
2 Correct 116 ms 3964 KB Output is correct
3 Correct 131 ms 3448 KB Output is correct
4 Correct 141 ms 3292 KB Output is correct
5 Correct 172 ms 6640 KB Output is correct
6 Correct 192 ms 6648 KB Output is correct
7 Correct 196 ms 6536 KB Output is correct
8 Correct 252 ms 6520 KB Output is correct
9 Correct 192 ms 6388 KB Output is correct
10 Correct 220 ms 6444 KB Output is correct
11 Correct 168 ms 6588 KB Output is correct
12 Correct 290 ms 6424 KB Output is correct