oj.uz

Submission #784568

# Submission time Handle Problem Language Result Execution time Memory
784568 2023-07-16T09:50:30 Z Acanikolic Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 130 ms 9420 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 1124 KB Output is correct
3 Correct 2 ms 1132 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1364 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1364 KB Output is correct
8 Correct 3 ms 1256 KB Output is correct
9 Correct 4 ms 1364 KB Output is correct
10 Correct 3 ms 1304 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 3 ms 1352 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1932 KB Output is correct
2 Correct 28 ms 1684 KB Output is correct
3 Correct 20 ms 1916 KB Output is correct
4 Correct 27 ms 2144 KB Output is correct
5 Correct 30 ms 2284 KB Output is correct
6 Correct 31 ms 2352 KB Output is correct
7 Correct 31 ms 2280 KB Output is correct
8 Correct 30 ms 2300 KB Output is correct
9 Correct 30 ms 2368 KB Output is correct
10 Correct 29 ms 2372 KB Output is correct
11 Correct 29 ms 2368 KB Output is correct
12 Correct 36 ms 2316 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4904 KB Output is correct
2 Correct 61 ms 5904 KB Output is correct
3 Correct 55 ms 4844 KB Output is correct
4 Correct 66 ms 4824 KB Output is correct
5 Correct 87 ms 9396 KB Output is correct
6 Correct 88 ms 9312 KB Output is correct
7 Correct 90 ms 9420 KB Output is correct
8 Correct 99 ms 9372 KB Output is correct
9 Correct 100 ms 9268 KB Output is correct
10 Correct 92 ms 9340 KB Output is correct
11 Correct 82 ms 9220 KB Output is correct
12 Correct 130 ms 9248 KB Output is correct