oj.uz

답안 #776413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
776413 2023-07-07T20:29:00 Z peuch Sterilizing Spray (JOI15_sterilizing) C++17
85 / 100
 719 ms 52264 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) {
			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> (50);
	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> (50);
	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: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 5 ms 9940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 12400 KB Output is correct
2 Correct 97 ms 28500 KB Output is correct
3 Correct 142 ms 28636 KB Output is correct
4 Correct 371 ms 20060 KB Output is correct
5 Correct 629 ms 51784 KB Output is correct
6 Correct 693 ms 51864 KB Output is correct
7 Correct 252 ms 50952 KB Output is correct
8 Correct 650 ms 51872 KB Output is correct
9 Correct 450 ms 51864 KB Output is correct
10 Correct 486 ms 51856 KB Output is correct
11 Correct 429 ms 51872 KB Output is correct
12 Correct 436 ms 51988 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 410 ms 31372 KB Output is correct
2 Correct 436 ms 31924 KB Output is correct
3 Correct 278 ms 28748 KB Output is correct
4 Correct 432 ms 23300 KB Output is correct
5 Correct 719 ms 52080 KB Output is correct
6 Correct 666 ms 52044 KB Output is correct
7 Correct 678 ms 51996 KB Output is correct
8 Correct 697 ms 52036 KB Output is correct
9 Correct 470 ms 52092 KB Output is correct
10 Correct 453 ms 52096 KB Output is correct
11 Correct 451 ms 52112 KB Output is correct
12 Correct 529 ms 52264 KB Output is correct