Submission #317289

#	Time	Username	Problem	Language	Result	Execution time	Memory
317289		hoangtung_pro	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	363 ms	7932 KiB

sterilizing

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define bit(s, i) (s & (1<<i))

using namespace std;

const int N = 1e5 + 5;
const int M = 1;
const int K = 1;
const int mod = 1e9+7;
const int inf = 2e9;
const long long Inf = 2e18;

typedef long long ll;
typedef pair < int, int > ii;

int n, q, k, a[N];

struct tree {
	long long sum;
	int ma;
} IT[4 * N];

void reset(int id, int l, int r, int pos) {
	if(l > pos || r < pos) return;

	if(l == r) {
		IT[id].sum = a[pos];
		IT[id].ma = a[pos];
		return;
	}

	int mid = (l + r) >> 1;

	reset(id<<1, l, mid, pos);
	reset(id<<1|1, mid + 1, r, pos);

	IT[id].sum = IT[id<<1].sum + IT[id<<1|1].sum;
	IT[id].ma = max(IT[id<<1].ma, IT[id<<1|1].ma);
}

void div(int id, int l, int r, int u, int v) {
	if(r < u || v < l) return;

	if(l == r) {
		IT[id].ma /= k;
		IT[id].sum /= k;
		return;
	}

	if(IT[id].ma == 0 || k == 1) return;

	int mid = (l + r) >> 1;

	div(id<<1, l, mid, u, v);
	div(id<<1|1, mid + 1, r, u, v);

	IT[id].ma = max(IT[id<<1].ma, IT[id<<1|1].ma);
	IT[id].sum = IT[id<<1].sum + IT[id<<1|1].sum;
}

long long get(int id, int l, int r, int u, int v) {
	if(r < u || v < l) return 0;

	if(u <= l && r <= v) return IT[id].sum;

	int mid = (l + r) >> 1;
	return get(id<<1, l, mid, u, v) + get(id<<1|1, mid + 1, r , u, v);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("trash.inp","r",stdin);
    // freopen("trash.out","w",stdout);

    cin >> n >> q >> k;
    
    for(int i=1;i<=n;++i) {
    	cin >> a[i];
		reset(1, 1, n, i);
	}

	for(int i=1;i<=q;++i) {
		int t, x, y;
		cin >> t >> x >> y;

		if(t == 1) {
			a[x] = y;
			reset(1, 1, n, x);
		}
		if(t == 2) {
			div(1, 1, n, x, y);
		}
		if(t == 3) {
			cout << get(1, 1, n, x, y) << endl;
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75