oj.uz

Submission #776417

# Submission time Handle Problem Language Result Execution time Memory
776417 2023-07-07T20:43:36 Z peuch Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 593 ms 42772 KB 
/*
	Idea:
	
	Represent C[i] in base K.
	Seg:
		Each node will save the representation in base K as a vector with the sum of values in each power.
		Merging is in O(log) by adding the vectors.
		Operation 1 is a point update changing the vector of a leaf node and recalculating the ancestors.
		Operation 2 is a lazy range update that will make seg[pos][i] = segp[pos][i + 1]
		Operation 3 is a range query by merging of range nodes and then computing the final value.
	
	O(Qlog(N)^2)

	Confidence 7/10
*/

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

const int MAXN = 100000 + 10;

int n, q, k;

int v[MAXN];
vector<int> seg[4 * MAXN];
int lz[4 * MAXN];

void refresh(int pos, int ini, int fim);
void build(int pos, int ini, int fim);
void updatePoint(int pos, int ini, int fim, int id, int val);
void updateRange(int pos, int ini, int fim, int p, int q);
vector<int> query(int pos, int ini, int fim, int p, int q);
void merge(vector<int>& ret, vector<int>& e, vector<int>& d);
long long unconv(vector<int> val);
void conv(vector<int>& ret, int val);

long long bit[MAXN];

void update1(int id, int val) {
	while(id < MAXN) {
		bit[id] += val;
		id += id & (-id);
	}
}

long long query1(int id) {
	long long ret = 0;
	while(id > 0) {
		ret += bit[id];
		id -= id&(-id);
	}
	return ret;
}

int main() {
	scanf("%d %d %d", &n, &q, &k);
	for(int i = 1; i <= n; i++)
		scanf("%d", &v[i]);

	if(k == 1) {
		for(int i = 1; i <= n; i++) {
			update1(i, v[i]);
		}
		for(int i = 1; i <= q; i++) {
			int s, a, b;
			scanf("%d %d %d", &s, &a, &b);
			if(s == 1) {
				update1(a, -v[a]);
				v[a] = b;
				update1(a, v[a]);
			}
			if(s == 3) {
				printf("%lld\n", query1(b) - query1(a - 1));
			}
		}
	}

	build(1, 1, n);

		// for(int i = 1; i <= n; i++) {
		// 	vector<int> aux = query(1, 1, n, i, i);
		// 	printf("%lld (", unconv(aux));
		// 	for(int j = 4; j >= 0; j--) {
		// 		printf("%d ", aux[j]);
		// 	}
		// 	printf(")");
		// }
		// printf("\n");

	for(int i = 1; i <= q; i++) {
		int s, a, b;
		scanf("%d %d %d", &s, &a, &b);
		if(s == 1) {
			updatePoint(1, 1, n, a, b);
		}
		if(s == 2) {
			if(k != 1) updateRange(1, 1, n, a, b);
		}
		if(s == 3) {
			vector<int> aux = query(1, 1, n, a, b);
			long long ans = unconv(aux);
			printf("%lld\n", ans);
		}

		// for(int i = 1; i <= n; i++) {
		// 	vector<int> aux = query(1, 1, n, i, i);
		// 	printf("%lld (", unconv(aux));
		// 	for(int j = 4; j >= 0; j--) {
		// 		printf("%d ", aux[j]);
		// 	}
		// 	printf(")");
		// }
		// printf("\n");
	}
}

void refresh(int pos, int ini, int fim) {
	if(lz[pos] == 0) return;
	if(k == 1) return;
	for(int i = 0; i < seg[pos].size(); i++) {
		if(i + lz[pos] >= seg[pos].size()) seg[pos][i] = 0;
		else seg[pos][i] = seg[pos][i + lz[pos]];
	}
	if(ini != fim) {
		int e = pos << 1, d = e | 1;
		lz[e] += lz[pos];
		lz[d] += lz[pos];
	}
	lz[pos] = 0;
}

void build(int pos, int ini, int fim) {
	if(ini == fim) {
		conv(seg[pos], v[ini]);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	build(e, ini, mid);
	build(d, mid + 1, fim);
	merge(seg[pos], seg[e], seg[d]);
}

void updatePoint(int pos, int ini, int fim, int id, int val) {
	refresh(pos, ini, fim);
	if(ini > id || fim < id) return;
	if(ini == fim) {
		conv(seg[pos], val);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	updatePoint(e, ini, mid, id, val);
	updatePoint(d, mid + 1, fim, id, val);
	merge(seg[pos], seg[e], seg[d]);
}

void updateRange(int pos, int ini, int fim, int p, int q) {
	refresh(pos, ini, fim);
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q) {
		lz[pos]++;
		refresh(pos, ini, fim);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	updateRange(e, ini, mid, p, q);
	updateRange(d, mid + 1, fim, p, q);
	merge(seg[pos], seg[e], seg[d]);
}

vector<int> query(int pos, int ini, int fim, int p, int q) {
	refresh(pos, ini, fim);
	if(ini > q || fim < p) return vector<int> (35);
	if(ini >= p && fim <= q) return seg[pos];
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	vector<int> eVal = query(e, ini, mid, p, q);
	vector<int> dVal = query(d, mid + 1, fim, p, q);
	vector<int> ret;
	merge(ret, eVal, dVal);
	return ret;
}

void merge(vector<int>& ret, vector<int>& e, vector<int>& d) {
	ret = vector<int> (e.size());
	for(int i = 0; i < e.size(); i++) {
		ret[i] = e[i] + d[i];
	}
}

long long unconv(vector<int> val) {
	long long ret = 0;
	for(int i = val.size() - 1; i >= 0; i--) {
		ret *= k;
		ret += val[i];
	}
	return ret;
}

void conv(vector<int>& ret, int val){
	ret = vector<int> (35);
	if(val == 0) return;
	int aux = 0;
	if(k == 1) ret[aux] = val, val = 0;
	while(val > 0) {
		ret[aux] = val % k;
		val /= k;
		aux++;
	}
}

Compilation message

sterilizing.cpp: In function 'void refresh(int, int, int)':
sterilizing.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int i = 0; i < seg[pos].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   if(i + lz[pos] >= seg[pos].size()) seg[pos][i] = 0;
      |      ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'void merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
sterilizing.cpp:184:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |  for(int i = 0; i < e.size(); i++) {
      |                 ~~^~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d %d", &n, &q, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d", &v[i]);
      |   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |    scanf("%d %d %d", &s, &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d %d %d", &s, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 4 ms 9940 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 10 ms 10068 KB Output is correct
5 Correct 13 ms 10708 KB Output is correct
6 Correct 15 ms 10696 KB Output is correct
7 Correct 12 ms 10708 KB Output is correct
8 Correct 12 ms 10580 KB Output is correct
9 Correct 12 ms 10696 KB Output is correct
10 Correct 12 ms 10580 KB Output is correct
11 Correct 15 ms 10708 KB Output is correct
12 Correct 14 ms 10708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 25844 KB Output is correct
2 Correct 44 ms 20868 KB Output is correct
3 Correct 55 ms 34980 KB Output is correct
4 Correct 70 ms 42112 KB Output is correct
5 Correct 91 ms 42744 KB Output is correct
6 Correct 78 ms 42620 KB Output is correct
7 Correct 75 ms 42648 KB Output is correct
8 Correct 77 ms 42536 KB Output is correct
9 Correct 76 ms 42612 KB Output is correct
10 Correct 81 ms 42772 KB Output is correct
11 Correct 74 ms 42644 KB Output is correct
12 Correct 76 ms 42612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 11852 KB Output is correct
2 Correct 79 ms 24408 KB Output is correct
3 Correct 109 ms 24432 KB Output is correct
4 Correct 312 ms 17796 KB Output is correct
5 Correct 534 ms 42456 KB Output is correct
6 Correct 523 ms 42460 KB Output is correct
7 Correct 80 ms 42260 KB Output is correct
8 Correct 520 ms 42444 KB Output is correct
9 Correct 417 ms 42460 KB Output is correct
10 Correct 344 ms 42484 KB Output is correct
11 Correct 353 ms 42584 KB Output is correct
12 Correct 356 ms 42392 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 26656 KB Output is correct
2 Correct 377 ms 26864 KB Output is correct
3 Correct 256 ms 24560 KB Output is correct
4 Correct 336 ms 20392 KB Output is correct
5 Correct 565 ms 42692 KB Output is correct
6 Correct 557 ms 42672 KB Output is correct
7 Correct 572 ms 42764 KB Output is correct
8 Correct 593 ms 42764 KB Output is correct
9 Correct 378 ms 42740 KB Output is correct
10 Correct 401 ms 42760 KB Output is correct
11 Correct 367 ms 42712 KB Output is correct
12 Correct 421 ms 42708 KB Output is correct