Submission #102038

#	Time	Username	Problem	Language	Result	Execution time	Memory
102038		tincamatei	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	925 ms	54544 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

const int MAX_CF = 32;
const int MAX_N = 100000;

struct KBaseNumber {
	int cf[MAX_CF];

	KBaseNumber() {
		for(int i = 0; i < MAX_CF; ++i)
			cf[i] = 0;
	}

} aint[1+4*MAX_N];
int lazy[1+4*MAX_N];

void shift(KBaseNumber &target, int nr) {
	for(int i = 0; i < MAX_CF; ++i)
		if(i + nr < MAX_CF)
			target.cf[i] = target.cf[i + nr];
		else
			target.cf[i] = 0;
}

void calcSum(int k, KBaseNumber &target, KBaseNumber &a, KBaseNumber &b) {
	for(int i = 0; i < MAX_CF; ++i)
		target.cf[i] = a.cf[i] + b.cf[i];
}

void pushLazy(int nod, int l, int r) {
	shift(aint[nod], lazy[nod]);
	if(l < r) {
		lazy[2 * nod] += lazy[nod];
		lazy[2 * nod + 1] += lazy[nod];
	}
	lazy[nod] = 0;
}

void setNumber(int poz, int x, int k, int l, int r, int nod = 1) {
	pushLazy(nod, l, r);
	if(poz < l || r < poz) return;
	
	if(l == r) {
		for(int i = 0; i < MAX_CF; ++i) {
			aint[nod].cf[i] = x % k;
			x /= k;
		}
	} else {
		int mid = (l + r) / 2;

		setNumber(poz, x, k, l, mid, 2 * nod);
		setNumber(poz, x, k, mid + 1, r, 2 * nod + 1);
	
		calcSum(k, aint[nod], aint[2 * nod], aint[2 * nod + 1]);
	}
}

void setShift(int i, int j, int k, int l, int r, int nod = 1) {
	pushLazy(nod, l, r);
	if(j < l || r < i) return;

	if(i <= l && r <= j) {
		lazy[nod]++;
		pushLazy(nod, l, r);
	} else if(l < r) {
		int mid = (l + r) / 2;
		
		setShift(i, j, k, l, mid, 2 * nod);
		setShift(i, j, k, mid + 1, r, 2 * nod + 1);
		
		calcSum(k, aint[nod], aint[2 * nod], aint[2 * nod + 1]);
	}
}

KBaseNumber query(int i, int j, int k, int l, int r, int nod = 1) {
	pushLazy(nod, l, r);
	if(j < l || r < i) return KBaseNumber();
	
	if(i <= l && r <= j)
		return aint[nod];
	else {
		int mid = (l + r) / 2;
		KBaseNumber rez;
		KBaseNumber rezl = query(i, j, k, l, mid, 2 * nod),
		            rezr = query(i, j, k, mid + 1, r, 2 * nod + 1);

		calcSum(k, rez, rezl, rezr);
		return rez;
	}
}

long long getRealVal(KBaseNumber &x, int k) {
	long long rez = 0, p = 1;
	for(int i = 0; i < MAX_CF; ++i) {
		rez = rez + p * x.cf[i];
		p = p * k;
	}
	return rez;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, q, k;
	fscanf(fin, "%d%d%d", &n, &q, &k);
	
	for(int i = 1; i <= n; ++i) {
		int x;
		fscanf(fin, "%d", &x);
		setNumber(i, x, max(k, 2), 1, n);
	}

	for(int i = 0; i < q; ++i) {
		int t, x, y;
		fscanf(fin, "%d%d%d", &t, &x, &y);
		if(t == 1)
			setNumber(x, y, max(k, 2), 1, n, 1);
		else if(t == 2 && k > 1)
			setShift(x, y, k, 1, n, 1);
		else if(t == 3) {
			KBaseNumber rez = query(x, y, max(k, 2), 1, n, 1);
			fprintf(fout, "%lld\n", getRealVal(rez, max(k, 2)));
		}
	}

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:113:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d%d", &n, &q, &k);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:117:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d", &x);
   ~~~~~~^~~~~~~~~~~~~~~
sterilizing.cpp:123:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d%d", &t, &x, &y);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75