oj.uz

Submission #264616

# Submission time Handle Problem Language Result Execution time Memory
264616 2020-08-14T08:01:06 Z Atalasion Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 130 ms 4472 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;
const int SQ = 320;

vector<int> buc[N / SQ + 10];
int n, k, q, a[N];
ll sm[N];

inline void relax(int id){
	int l = id * SQ, r = min(n, (id + 1) * SQ);
	sm[id] = 0;
	buc[id].clear();
	for (int i = l; i < r; i++){
		if (a[i]) sm[id] += a[i], buc[id].pb(i);
	}
	return;
}

inline void Ch(int l, int r){
	if (k == 1) return;
	while (l < r){
		if (l % SQ == 0 && l + SQ <= r){
			vi qq;
			for (auto u:buc[l / SQ]){
				sm[l / SQ] -= a[u];
				a[u] = a[u] / k;
				sm[l / SQ] += a[u];
				if (a[u]) qq.pb(u);
			}
			buc[l / SQ].clear();
			buc[l / SQ].swap(qq);
			l += SQ;	
		}else{
			a[l] /= k;
			l++;
		}
	}
	relax(l / SQ);
	relax((r - 1) / SQ);
	return;
}

ll Sum(int l, int r){
	ll res = 0;
	while (l < r){
		if (l % SQ == 0 && l + SQ <= r){
			res += sm[l / SQ];
			l += SQ;
		}else res += a[l], l++;
	}
	return res;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++){
		if (a[i]) buc[i / SQ].pb(i);
		sm[i / SQ] += a[i];
	}
	for (int i = 1; i <= q; i++){
		int x, l, r;
		cin >> x >> l >> r;
		l--;
		if (x == 1){
			a[l] = r;
			relax(l / SQ);
		}else if(x == 2){
			Ch(l, r);
		}else cout << Sum(l, r) << '\n';
	}









	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3208 KB Output is correct
2 Correct 78 ms 2768 KB Output is correct
3 Correct 81 ms 3192 KB Output is correct
4 Correct 87 ms 3960 KB Output is correct
5 Correct 103 ms 4472 KB Output is correct
6 Correct 112 ms 4300 KB Output is correct
7 Correct 100 ms 4472 KB Output is correct
8 Correct 99 ms 4344 KB Output is correct
9 Correct 112 ms 4216 KB Output is correct
10 Correct 112 ms 4216 KB Output is correct
11 Correct 115 ms 4180 KB Output is correct
12 Correct 117 ms 4176 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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