oj.uz

Submission #562795

# Submission time Handle Problem Language Result Execution time Memory
562795 2022-05-15T10:03:46 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 222 ms 4504 KB 
#include <bits/stdc++.h>
using namespace std;
struct binary_indexed_tree{
  int N;
  vector<long long> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i, int x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  long long sum(int i){
    long long ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  long long sum(int L, int R){
    return sum(R) - sum(L);
  }
};
int main(){
  int N, Q, K;
  cin >> N >> Q >> K;
  vector<int> C(N);
  for (int i = 0; i < N; i++){
    cin >> C[i];
  }
  binary_indexed_tree BIT(N);
  for (int i = 0; i < N; i++){
    BIT.add(i, C[i]);
  }
  for (int i = 0; i < Q; i++){
    int S, T, U;
    cin >> S >> T >> U;
    if (S == 1){
      T--;
      BIT.add(T, -C[T]);
      C[T] = U;
      BIT.add(T, U);
    }
    if (S == 3){
      T--;
      cout << BIT.sum(T, U) << endl;
    }
  }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 2044 KB Output is correct
2 Correct 124 ms 2576 KB Output is correct
3 Correct 119 ms 2864 KB Output is correct
4 Correct 148 ms 3296 KB Output is correct
5 Correct 177 ms 4328 KB Output is correct
6 Correct 222 ms 4380 KB Output is correct
7 Correct 177 ms 4504 KB Output is correct
8 Correct 164 ms 4340 KB Output is correct
9 Correct 183 ms 4248 KB Output is correct
10 Correct 166 ms 4284 KB Output is correct
11 Correct 176 ms 4240 KB Output is correct
12 Correct 175 ms 4248 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 1964 KB Output isn't correct
2 Halted 0 ms 0 KB -