oj.uz

Submission #264679

# Submission time Handle Problem Language Result Execution time Memory
264679 2020-08-14T08:22:33 Z Atalasion Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 2161 ms 5056 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")
#define int long long

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 = 2;

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 Incorrect 3 ms 1536 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 276 ms 3500 KB Output is correct
2 Correct 184 ms 3040 KB Output is correct
3 Correct 293 ms 4088 KB Output is correct
4 Correct 445 ms 4796 KB Output is correct
5 Correct 587 ms 4856 KB Output is correct
6 Correct 560 ms 5056 KB Output is correct
7 Correct 598 ms 4892 KB Output is correct
8 Correct 598 ms 4920 KB Output is correct
9 Correct 2077 ms 4940 KB Output is correct
10 Correct 2161 ms 4984 KB Output is correct
11 Correct 1965 ms 4992 KB Output is correct
12 Correct 1909 ms 5016 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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