제출 #776417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776417		peuch	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	593 ms	42772 KiB

sterilizing

/*
	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++;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75