oj.uz

Submission #485353

# Submission time Handle Problem Language Result Execution time Memory
485353 2021-11-07T08:35:01 Z MilosMilutinovic Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 224 ms 7536 KB 
/**
 *    author: m371
 *    created: 06.11.2021 23:29:50
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

const int N = 1e5 + 5;
const int MAX = 4 * N;

int n, q, k;
long long mx[MAX], sum[MAX];
          
void modify(int x, int l, int r, int pos, int val) {
  if (l == r) {
    mx[x] = sum[x] = val;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) {
    modify(x + x, l, mid, pos, val);
  } else {
    modify(x + x + 1, mid + 1, r, pos, val);
  }   
  mx[x] = max(mx[x + x], mx[x + x + 1]);
  sum[x] = sum[x + x] + sum[x + x + 1];
}

void update(int x, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll || mx[x] == 0) {
    return;
  }
  if (l == r) {
    mx[x] = sum[x] = (mx[x] / k);
    return;
  }
  int mid = l + r >> 1;
  update(x + x, l, mid, ll, rr);
  update(x + x + 1, mid + 1, r, ll, rr);
  mx[x] = max(mx[x + x], mx[x + x + 1]);
  sum[x] = sum[x + x] + sum[x + x + 1];
}
                                         
long long get(int x, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll) return 0;
  if (ll <= l && r <= rr) return sum[x];
  int mid = l + r >> 1;
  return get(x + x, l, mid, ll, rr) + get(x + x + 1, mid + 1, r, ll, rr);
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0); 
  cin >> n >> q >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (k == 1) {
    fenwick<long long> fenw(n);
    for (int i = 0; i < n; i++) {
      fenw.modify(i, a[i]);
    }
    while (q--) {
      int foo;
      cin >> foo;
      if (foo == 1) {
        int pos, val;
        cin >> pos >> val;
        --pos;
        fenw.modify(pos, val - a[pos]);
        a[pos] = val;
      }
      if (foo == 2) {
        int l, r;
        cin >> l >> r;
      }
      if (foo == 3) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << fenw.get(r) - fenw.get(l - 1) << '\n';
      }
    }
  } else {
    for (int i = 0; i < n; i++) {
      modify(1, 0, n - 1, i, a[i]);
    }
    for (int i = 0; i < q; i++) {
      int foo;
      cin >> foo;
      if (foo == 1) {
        int pos, val;
        cin >> pos >> val;
        --pos;
        modify(1, 0, n - 1, pos, val);
      } 
      if (foo == 2) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        update(1, 0, n - 1, l, r);
      }
      if (foo == 3) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << get(1, 0, n - 1, l, r) << '\n';
      }
    }
  }
  return 0;
}

Compilation message

sterilizing.cpp: In function 'void modify(int, int, int, int, int)':
sterilizing.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid = l + r >> 1;
      |             ~~^~~
sterilizing.cpp: In function 'void update(int, int, int, int, int)':
sterilizing.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   int mid = l + r >> 1;
      |             ~~^~~
sterilizing.cpp: In function 'long long int get(int, int, int, int, int)':
sterilizing.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 5 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1604 KB Output is correct
2 Correct 28 ms 1352 KB Output is correct
3 Correct 28 ms 1788 KB Output is correct
4 Correct 30 ms 2124 KB Output is correct
5 Correct 40 ms 2296 KB Output is correct
6 Correct 38 ms 2116 KB Output is correct
7 Correct 36 ms 2120 KB Output is correct
8 Correct 36 ms 2132 KB Output is correct
9 Correct 38 ms 2220 KB Output is correct
10 Correct 36 ms 2208 KB Output is correct
11 Correct 37 ms 2244 KB Output is correct
12 Correct 40 ms 2236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 972 KB Output is correct
2 Correct 14 ms 2764 KB Output is correct
3 Correct 19 ms 2976 KB Output is correct
4 Correct 42 ms 2688 KB Output is correct
5 Correct 60 ms 6288 KB Output is correct
6 Correct 60 ms 6216 KB Output is correct
7 Correct 29 ms 3036 KB Output is correct
8 Correct 65 ms 6224 KB Output is correct
9 Correct 61 ms 6084 KB Output is correct
10 Correct 57 ms 6128 KB Output is correct
11 Correct 54 ms 6084 KB Output is correct
12 Correct 56 ms 6128 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3780 KB Output is correct
2 Correct 89 ms 4456 KB Output is correct
3 Correct 99 ms 3852 KB Output is correct
4 Correct 101 ms 3396 KB Output is correct
5 Correct 119 ms 7492 KB Output is correct
6 Correct 138 ms 7488 KB Output is correct
7 Correct 123 ms 7536 KB Output is correct
8 Correct 169 ms 7492 KB Output is correct
9 Correct 149 ms 7368 KB Output is correct
10 Correct 170 ms 7360 KB Output is correct
11 Correct 132 ms 7376 KB Output is correct
12 Correct 224 ms 7360 KB Output is correct