Submission #776414

#	Time	Username	Problem	Language	Result	Execution time	Memory
776414		peuch	Election Campaign (JOI15_election_campaign)	C++17	0 / 100	136 ms	41296 KiB

election_campaign

/*
	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]);
	assert(k != 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 (stderr)

election_campaign.cpp: In function 'void refresh(int, int, int)':
election_campaign.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i = 0; i < seg[pos].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   if(i + lz[pos] >= seg[pos].size()) seg[pos][i] = 0;
      |      ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
election_campaign.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for(int i = 0; i < e.size(); i++) {
      |                 ~~^~~~~~~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.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);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.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]);
      |   ~~~~~^~~~~~~~~~~~~
election_campaign.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d %d %d", &s, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40