제출 #264687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
264687		Atalasion	Sterilizing Spray (JOI15_sterilizing)	C++14	15 / 100	5098 ms	10100 KiB

sterilizing

//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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75