oj.uz

Submission #784566

# Submission time Handle Problem Language Result Execution time Memory
784566 2023-07-16T09:40:01 Z Acanikolic Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 36 ms 4812 KB 
#include <bits/stdc++.h>
 
#define ll long long 

#define int long long 
 
#define pb push_back 

#define F first
 
#define S second
 
using namespace std;
 
const long long N = 1e5+10;
 
const long long mod = 1e9+7;
 
const long long inf = 1e18;

vector<int>ft(N);

void update(int index,int n,int val) {
	while(index <= n) {
		ft[index] += val;
		index += index & -index; 
	}
}

int get(int x) {
	int X = 0;
	while(x >= 1) {
		X += ft[x];
		x -= x & -x;
	}
	return X;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	int n,Q,k;
	cin >> n >> Q >> k;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++) {
		cin >> a[i];
		update(i,n,a[i]);
	}
	if(k == 1) {
		while(Q--) {
			int type;
			cin >> type;
			if(type == 1) {
				int index,val;
				cin >> index >> val;
				update(index,n,val-a[index]);
				a[index] = val;
			}
			else if(type == 2) {
				int l,r;
				cin >> l >> r;
			}
			else {
				int l,r;
				cin >> l >> r;
				cout << get(r)-get(l-1) << '\n';
			}
		}
		return 0;
	}
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1108 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 24 ms 1892 KB Output is correct
2 Correct 26 ms 3328 KB Output is correct
3 Correct 21 ms 3676 KB Output is correct
4 Correct 26 ms 4348 KB Output is correct
5 Correct 30 ms 4812 KB Output is correct
6 Correct 30 ms 4700 KB Output is correct
7 Correct 31 ms 4784 KB Output is correct
8 Correct 32 ms 4704 KB Output is correct
9 Correct 30 ms 4728 KB Output is correct
10 Correct 30 ms 4656 KB Output is correct
11 Correct 36 ms 4684 KB Output is correct
12 Correct 30 ms 4680 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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