oj.uz

Submission #784570

# Submission time Handle Problem Language Result Execution time Memory
784570 2023-07-16T09:52:34 Z Acanikolic Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 113 ms 7740 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;
	}
	set<int>st;
	for(int i=1;i<=n;i++) {
		if(a[i] >= 1) st.insert(i);
	}
	while(Q--) {
		int type;
		cin >> type;
		if(type == 1) {
			int index,val;
			cin >> index >> val;
			update(index,n,val-a[index]);
			a[index] = val;
			if(st.find(index) == st.end() && val >= 1) st.insert(index);
		}
		else if(type == 2) {
			int l,r;
			cin >> l >> r;
			auto lb = st.lower_bound(l);
			vector<int>X;
			//cout << "menjam : ";
			for(lb;lb!=st.end()&&*lb<=r;lb++) {
				int x = a[*lb]/k;
				update(*lb,n,x-a[*lb]);
				//cout << *lb << ' ' << get(*lb)-get(*lb-1) << endl;
				a[*lb] = x;
				if(a[*lb] == 0) X.pb(*lb);
			}
			//cout << endl;
			for(int i=0;i<X.size();i++) st.erase(X[i]);
			//for(int i=1;i<=n;i++) cout << get(i) << ' ';
			//cout << endl;
		}
		else {
			int l,r;
			cin >> l >> r;
			cout << get(r)-get(l-1) << '\n';
		}
	}
    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:93:8: warning: statement has no effect [-Wunused-value]
   93 |    for(lb;lb!=st.end()&&*lb<=r;lb++) {
      |        ^~
sterilizing.cpp:101:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    for(int i=0;i<X.size();i++) st.erase(X[i]);
      |                ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1888 KB Output is correct
2 Correct 21 ms 1776 KB Output is correct
3 Correct 20 ms 2000 KB Output is correct
4 Correct 25 ms 2224 KB Output is correct
5 Correct 29 ms 2264 KB Output is correct
6 Correct 29 ms 2292 KB Output is correct
7 Correct 29 ms 2292 KB Output is correct
8 Correct 29 ms 2324 KB Output is correct
9 Correct 28 ms 2288 KB Output is correct
10 Correct 29 ms 2360 KB Output is correct
11 Correct 28 ms 2320 KB Output is correct
12 Correct 29 ms 2352 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1368 KB Output is correct
2 Correct 11 ms 2740 KB Output is correct
3 Correct 14 ms 3052 KB Output is correct
4 Correct 27 ms 3124 KB Output is correct
5 Correct 41 ms 5772 KB Output is correct
6 Correct 41 ms 5784 KB Output is correct
7 Correct 25 ms 3404 KB Output is correct
8 Correct 40 ms 5808 KB Output is correct
9 Correct 36 ms 5600 KB Output is correct
10 Correct 36 ms 5668 KB Output is correct
11 Correct 36 ms 5656 KB Output is correct
12 Correct 36 ms 5692 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4172 KB Output is correct
2 Correct 50 ms 4124 KB Output is correct
3 Correct 54 ms 3728 KB Output is correct
4 Correct 53 ms 3120 KB Output is correct
5 Correct 83 ms 6964 KB Output is correct
6 Correct 95 ms 6968 KB Output is correct
7 Correct 79 ms 6852 KB Output is correct
8 Correct 103 ms 6924 KB Output is correct
9 Correct 84 ms 7732 KB Output is correct
10 Correct 96 ms 7256 KB Output is correct
11 Correct 80 ms 7740 KB Output is correct
12 Correct 113 ms 7284 KB Output is correct