oj.uz

Submission #102038

# Submission time Handle Problem Language Result Execution time Memory
102038 2019-03-21T20:15:03 Z tincamatei Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 925 ms 54544 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 50424 KB Output is correct
2 Correct 50 ms 50552 KB Output is correct
3 Correct 47 ms 50424 KB Output is correct
4 Correct 59 ms 50652 KB Output is correct
5 Correct 63 ms 50608 KB Output is correct
6 Correct 63 ms 50572 KB Output is correct
7 Correct 63 ms 50552 KB Output is correct
8 Correct 59 ms 50552 KB Output is correct
9 Correct 61 ms 50556 KB Output is correct
10 Correct 63 ms 50552 KB Output is correct
11 Correct 75 ms 50552 KB Output is correct
12 Correct 64 ms 50552 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 53428 KB Output is correct
2 Correct 342 ms 53112 KB Output is correct
3 Correct 431 ms 53488 KB Output is correct
4 Correct 598 ms 54184 KB Output is correct
5 Correct 636 ms 54520 KB Output is correct
6 Correct 611 ms 54460 KB Output is correct
7 Correct 595 ms 54544 KB Output is correct
8 Correct 572 ms 54520 KB Output is correct
9 Correct 548 ms 54508 KB Output is correct
10 Correct 538 ms 54264 KB Output is correct
11 Correct 548 ms 54340 KB Output is correct
12 Correct 522 ms 54320 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 51060 KB Output is correct
2 Correct 216 ms 51284 KB Output is correct
3 Correct 305 ms 51380 KB Output is correct
4 Correct 459 ms 52088 KB Output is correct
5 Correct 811 ms 53112 KB Output is correct
6 Correct 811 ms 52984 KB Output is correct
7 Correct 574 ms 53144 KB Output is correct
8 Correct 800 ms 53240 KB Output is correct
9 Correct 713 ms 52788 KB Output is correct
10 Correct 672 ms 52980 KB Output is correct
11 Correct 634 ms 52984 KB Output is correct
12 Correct 697 ms 52984 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 52784 KB Output is correct
2 Correct 539 ms 53068 KB Output is correct
3 Correct 474 ms 52416 KB Output is correct
4 Correct 601 ms 52856 KB Output is correct
5 Correct 919 ms 54344 KB Output is correct
6 Correct 909 ms 54236 KB Output is correct
7 Correct 910 ms 54396 KB Output is correct
8 Correct 925 ms 54520 KB Output is correct
9 Correct 851 ms 54268 KB Output is correct
10 Correct 736 ms 54224 KB Output is correct
11 Correct 701 ms 54184 KB Output is correct
12 Correct 743 ms 54196 KB Output is correct