oj.uz

Submission #23025

# Submission time Handle Problem Language Result Execution time Memory
23025 2017-05-01T23:45:42 Z shuuna Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 250024 KB 
//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

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

# Verdict Execution time Memory Grader output
1 Correct 136 ms 250016 KB Output is correct
2 Correct 0 ms 250020 KB Output is correct
3 Correct 73 ms 250024 KB Output is correct
4 Correct 173 ms 250020 KB Output is correct
5 Correct 203 ms 250020 KB Output is correct
6 Correct 233 ms 250016 KB Output is correct
7 Correct 149 ms 250020 KB Output is correct
8 Correct 159 ms 250016 KB Output is correct
9 Correct 243 ms 250020 KB Output is correct
10 Correct 229 ms 250016 KB Output is correct
11 Correct 229 ms 250020 KB Output is correct
12 Correct 216 ms 250024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 250020 KB Output is correct
2 Correct 39 ms 250020 KB Output is correct
3 Correct 46 ms 250016 KB Output is correct
4 Correct 96 ms 250020 KB Output is correct
5 Correct 69 ms 250020 KB Output is correct
6 Correct 66 ms 250020 KB Output is correct
7 Correct 89 ms 250020 KB Output is correct
8 Correct 83 ms 250016 KB Output is correct
9 Correct 63 ms 250016 KB Output is correct
10 Correct 73 ms 250016 KB Output is correct
11 Correct 56 ms 250016 KB Output is correct
12 Correct 73 ms 250020 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1849 ms 250016 KB Output is correct
2 Correct 1843 ms 250020 KB Output is correct
3 Correct 2589 ms 250024 KB Output is correct
4 Execution timed out 5000 ms 250020 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 250016 KB Execution timed out
2 Halted 0 ms 0 KB -