oj.uz

답안 #776408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
776408 2023-07-07T20:17:40 Z peuch Sterilizing Spray (JOI15_sterilizing) C++17
85 / 100
 652 ms 42808 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);

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

	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) {
			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);
	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:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 0; i < seg[pos].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   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:148:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  for(int i = 0; i < e.size(); i++) {
      |                 ~~^~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d %d %d", &n, &q, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &v[i]);
      |   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d %d %d", &s, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Incorrect 6 ms 9952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 297 ms 25968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 11792 KB Output is correct
2 Correct 82 ms 24388 KB Output is correct
3 Correct 128 ms 24428 KB Output is correct
4 Correct 367 ms 17868 KB Output is correct
5 Correct 569 ms 42408 KB Output is correct
6 Correct 596 ms 42432 KB Output is correct
7 Correct 411 ms 42616 KB Output is correct
8 Correct 592 ms 42460 KB Output is correct
9 Correct 454 ms 42560 KB Output is correct
10 Correct 410 ms 42472 KB Output is correct
11 Correct 413 ms 42440 KB Output is correct
12 Correct 375 ms 42412 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 26636 KB Output is correct
2 Correct 408 ms 26848 KB Output is correct
3 Correct 266 ms 24544 KB Output is correct
4 Correct 369 ms 20432 KB Output is correct
5 Correct 652 ms 42704 KB Output is correct
6 Correct 635 ms 42808 KB Output is correct
7 Correct 601 ms 42696 KB Output is correct
8 Correct 599 ms 42700 KB Output is correct
9 Correct 403 ms 42736 KB Output is correct
10 Correct 402 ms 42712 KB Output is correct
11 Correct 396 ms 42728 KB Output is correct
12 Correct 418 ms 42748 KB Output is correct