Submission #23025

#	Time	Username	Problem	Language	Result	Execution time	Memory
23025		shuuna	Sterilizing Spray (JOI15_sterilizing)	C++14	15 / 100	5000 ms	250024 KiB

sterilizing

//THIS IS ONLY TRIAL. SOLUTION TAKEN FROM KAGAMIZ BLOG
#include <bits/stdc++.h>

#define MAX_N (100010)
#define MAX_Q (100010)
#define MAX_S (131072)

using namespace std;

typedef long long Int;

class BIT {
	Int A[MAX_N + 1];
public:
	BIT(){
		memset(A, 0, sizeof(A));
	}
	void add(int p, Int x){
		for (p++; p <= MAX_N; p += p & -p) A[p] += x;
	}
	Int sum(int p){
		Int ret = 0;
		for (p++; p; p &= (p - 1)) ret += A[p];
		return (ret);
	}
};

struct Node {
	Int val;
	bool id;
	bool reset;
	Node *ch[2];
};

Node seg[30][2 * MAX_S - 1];

int pos, idx = 0;
Node *parents[30][32], *children[30][32];

inline void evaluate(Node *p)
{
	if (p->reset){
		p->val = 0;
		if (p->ch[0] != nullptr) p->ch[0]->reset = true;
		if (p->ch[1] != nullptr) p->ch[1]->reset = true;
	}
	p->reset = false;
}

inline void updateNode(Node *p)
{
	p->val = p->ch[0]->val + p->ch[1]->val;
}

void update(Node *p, int a, int b, int x, int l = 0, int r = MAX_S)
{
	evaluate(p);
	if (b <= l || r <= a) return;
	if (a <= l && r <= b){
		p->val = x;
		return;
	}
	update(p->ch[0], a, b, x, l, (l + r) / 2);
	update(p->ch[1], a, b, x, (l + r) / 2, r);
	updateNode(p);
}

void getInterval(Node *p, Node *pp, int a, int b, int l = 0, int r = MAX_S)
{
	if (b <= l || r <= a) return;
	if (a <= l && r <= b){
		parents[pos][idx] = pp;
		children[pos][idx++] = p;
		return;
	}
	getInterval(p->ch[0], p, a, b, l, (l + r) / 2);
	getInterval(p->ch[1], p, a, b, (l + r) / 2, r);
}

void modify(Node *p, int a, int b, int l = 0, int r = MAX_S)
{
	evaluate(p);
	if (b <= l || r <= a) return;
	if (a <= l && r <= b) return;
	modify(p->ch[0], a, b, l, (l + r) / 2);
	modify(p->ch[1], a, b, (l + r) / 2, r);
	updateNode(p);
}

void clear(Node *p, int a, int b, int l = 0, int r = MAX_S)
{
	evaluate(p);
	if (b <= l || r <= a) return;
	if (a <= l && r <= b){
		p->reset = true;
		evaluate(p);
		return;
	}
	clear(p->ch[0], a, b, l, (l + r) / 2);
	clear(p->ch[1], a, b, (l + r) / 2, r);
	updateNode(p);
}

Int getSum(Node *p, int a, int b, int l = 0, int r = MAX_S)
{
	evaluate(p);
	if (b <= l || r <= a) return (0);
	if (a <= l && r <= b) return (p->val);
	Int lsum = getSum(p->ch[0], a, b, l, (l + r) / 2);
	Int rsum = getSum(p->ch[1], a, b, (l + r) / 2, r);
	updateNode(p);
	return (lsum + rsum);
}

int C[MAX_N];
int S[MAX_Q], T[MAX_Q], U[MAX_Q];

int main()
{
	int N, Q, K;

	scanf("%d %d %d", &N, &Q, &K);

	for (int i = 0; i < N; i++){
		scanf("%d", C + i);
	}

	for (int i = 0; i < Q; i++){
		scanf("%d %d %d", S + i, T + i, U + i);
	}

	if (K == 1){
		BIT bit;
		for (int i = 0; i < N; i++) bit.add(i, C[i]);
		for (int i = 0; i < Q; i++){
			if (S[i] == 1){
				bit.add(T[i] - 1, (Int)U[i] - C[T[i] - 1]);
				C[T[i] - 1] = U[i];
			}
			else if (S[i] == 3){
				printf("%lld\n", bit.sum(U[i] - 1) - bit.sum(T[i] - 2));
			}
		}
		return (0);
	}

	for (int i = 0; i < 30; i++){
		for (int j = 0; j < 2 * MAX_S - 1; j++){
			if (j < MAX_S - 1){
				seg[i][j].ch[0] = &seg[i][j * 2 + 1];
				seg[i][j].ch[1] = &seg[i][j * 2 + 2];
			}
			else {
				seg[i][j].ch[0] = nullptr;
				seg[i][j].ch[1] = nullptr;
			}

			seg[i][j].id = (j + 1) % 2;
			seg[i][j].reset = false;
			seg[i][j].val = 0;
		}
	}

	for (int i = 0; i < N; i++){
		Int v = C[i];
		for (int j = 0; j < 30; j++){
			Int s = v % K;
			update(&seg[j][0], i, i + 1, s);
			v /= K;
		}
	}

	int ct = 0;
	for (int i = 0; i < Q; i++){
		if (S[i] == 1){
			Int v = U[i];
			for (int j = 0; j < 30; j++){
				Int s = v % K;
				update(&seg[j][0], T[i] - 1, T[i], s);
				v /= K;
			}
		}
		if (S[i] == 2){
			for (int j = 0; j < 30; j++){
				modify(&seg[j][0], T[i] - 1, U[i]);
			}

			clear(&seg[0][0], T[i] - 1, U[i]);

			for (int j = 0; j < 30; j++){
				pos = j;
				idx = 0;
				getInterval(&seg[j][0], nullptr, T[i] - 1, U[i]);
			}

			for (int j = 0; j < idx; j++){
				int id = children[0][j]->id;
				for (int k = 0; k < 30; k++){
					parents[k][j]->ch[id] = children[(k + 1) % 30][j];
				}
			}
			for (int j = 0; j < 30; j++){
				modify(&seg[j][0], T[i] - 1, U[i]);
			}
			ct++;
		}
		if (S[i] == 3){
			Int pK = 1;
			Int ans = 0;
			for (int j = 0; j < 30; j++){
				ans += pK * getSum(&seg[j][0], T[i] - 1, U[i]);
				pK *= K;
			}
			printf("%lld\n", ans);
		}
	}

	return (0);
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:122:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &Q, &K);
                               ^
sterilizing.cpp:125:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C + i);
                     ^
sterilizing.cpp:129:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", S + i, T + i, U + i);
                                         ^

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