oj.uz

Submission #264687

# Submission time Handle Problem Language Result Execution time Memory
264687 2020-08-14T08:24:00 Z Atalasion Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 10100 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 = 1;

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 9 ms 2816 KB Output is correct
5 Correct 12 ms 2960 KB Output is correct
6 Correct 9 ms 2944 KB Output is correct
7 Correct 8 ms 2884 KB Output is correct
8 Correct 12 ms 2944 KB Output is correct
9 Correct 10 ms 2944 KB Output is correct
10 Correct 9 ms 2944 KB Output is correct
11 Correct 9 ms 2944 KB Output is correct
12 Correct 9 ms 2944 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 5496 KB Output is correct
2 Correct 110 ms 4664 KB Output is correct
3 Correct 131 ms 6648 KB Output is correct
4 Correct 187 ms 7672 KB Output is correct
5 Correct 246 ms 7800 KB Output is correct
6 Correct 237 ms 7928 KB Output is correct
7 Correct 225 ms 7800 KB Output is correct
8 Correct 236 ms 7928 KB Output is correct
9 Correct 768 ms 7860 KB Output is correct
10 Correct 716 ms 7928 KB Output is correct
11 Correct 709 ms 7928 KB Output is correct
12 Correct 701 ms 7928 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 3072 KB Output is correct
2 Correct 233 ms 4472 KB Output is correct
3 Correct 366 ms 4512 KB Output is correct
4 Correct 816 ms 4732 KB Output is correct
5 Correct 3869 ms 7300 KB Output is correct
6 Correct 3516 ms 7320 KB Output is correct
7 Correct 240 ms 7696 KB Output is correct
8 Correct 3685 ms 7436 KB Output is correct
9 Execution timed out 5098 ms 6520 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 5328 KB Output is correct
2 Correct 1618 ms 7100 KB Output is correct
3 Correct 829 ms 6264 KB Output is correct
4 Correct 1106 ms 6196 KB Output is correct
5 Correct 3663 ms 10092 KB Output is correct
6 Correct 3636 ms 10100 KB Output is correct
7 Correct 3685 ms 10064 KB Output is correct
8 Correct 3779 ms 10096 KB Output is correct
9 Execution timed out 5082 ms 9180 KB Time limit exceeded
10 Halted 0 ms 0 KB -