Submission #1271236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271236		thieunguyenhuy	Sterilizing Spray (JOI15_sterilizing)	C++20	0 / 100	940 ms	7472 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);
}
unsigned long long random(unsigned long long l, unsigned long long r) {
    return uniform_int_distribution<unsigned long long>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1e5 + 5, SQR = 1, NUM_BLOCKS = N / SQR + 5, LG = 31;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

int n, q, k;
int c[N], blockId[N];
int cnt[NUM_BLOCKS], sum[NUM_BLOCKS][LG];

void freeBlock(int id) {
	for (int i = 0; i < LG; ++i) sum[id][i] = 0;
	for (int i = id * SQR; i < min(n, (id + 1) * SQR); ++i) {
		for (int _ = 0; _ < cnt[id]; ++_) c[i] /= k;
		for (int j = 0, tmp = c[i]; j < LG; ++j) sum[id][j] += tmp, tmp /= k;
	}
	cnt[id] = 0;
}

void update_single(int p, int val) {
	int id = blockId[p];
	for (int j = 0, tmp = c[p]; j < LG; ++j) sum[id][j] -= tmp, tmp /= k;
	c[p] = val;
	for (int j = 0, tmp = c[p]; j < LG; ++j) sum[id][j] += tmp, tmp /= k; 
}

void update(int l, int r) {
	int blockL = (l + SQR - 1) / SQR, blockR = blockId[r];

	if (blockL >= blockR) {
		freeBlock(blockR);
		for (int i = l; i <= r; ++i) update_single(i, c[i] / k);
		return;
	}

	for (int i = blockL; i < blockR; ++i) ++cnt[i];

	freeBlock(blockId[l]), freeBlock(blockR);
	for (int i = l; i < blockL * SQR; ++i) update_single(i, c[i] / k);
	for (int i = blockR * SQR; i <= r; ++i) update_single(i, c[i] / k);
}

ll get(int l, int r) {
	int blockL = (l + SQR - 1) / SQR, blockR = blockId[r];
	ll ans = 0;

	if (blockL >= blockR) {
		freeBlock(blockR);
		for (int i = l; i <= r; ++i) ans += c[i];
		return ans;
	}

	for (int i = blockL; i < blockR; ++i) {
		if (cnt[i] < LG) ans += sum[i][cnt[i]];
	}

	freeBlock(blockId[l]), freeBlock(blockR);
	for (int i = l; i < blockL * SQR; ++i) ans += c[i];
	for (int i = blockR * SQR; i <= r; ++i) ans += c[i];
	return ans;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> q >> k;

    assert(k != 1);

    for (int i = 0; i < n; ++i) cin >> c[i], blockId[i] = i / SQR;

    for (int i = 0; i < n; ++i) update_single(i, c[i]);

    // cerr << get(0, n - 1) << '\n';

    for (int i = 1; i <= q; ++i) {
    	int type, x, y; cin >> type >> x >> y;
    	if (type == 1) {
    		--x; freeBlock(blockId[x]);
    		update_single(x, y);
    	}
    	if (type == 2) {
    		--x, --y;
    		update(x, y);
    	}
    	if (type == 3) {
    		--x, --y;
    		cout << get(x, y) << '\n';
    	}

    	// cerr << "get " << get(0, n - 1) << '\n';
    	// for (int j = 0; j < n; ++j) cerr << c[j] << ' ';
    	// cerr << '\n';
    }

    return 0;
}

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