Submission #948994

#	Time	Username	Problem	Language	Result	Execution time	Memory
948994		rainboy	Watering can (POI13_kon)	C11	100 / 100	177 ms	22272 KiB

kon

#include <string.h>

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int n;
int ft[N];
int st[N_ * 2], lz[N_], h_, n_;

void ft_update(int i) {
	while (i < n) {
		ft[i]++;
		i |= i + 1;
	}
}

int ft_query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

void put(int i, int x) {
	st[i] += x;
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i])
		st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void purge(int i) {
	if (st[i] > 0)
		return;
	if (i >= n_) {
		st[i] = INF;
		ft_update(i - n_);
		return;
	}
	pus(i);
	purge(i << 1 | 0), purge(i << 1 | 1);
	pul(i);
}

void inicjuj(int n1, int k, int *dd) {
	int i;

	n = n1;
	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	memset(st, 0x3f, n_ * 2 * sizeof *st);
	memset(lz, 0, n_ * sizeof *lz);
	for (i = 0; i < n; i++)
		st[n_ + i] = k - dd[i];
	for (i = n_ - 1; i > 0; i--)
		pul(i);
	purge(1);
}

void podlej(int l, int r) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, -1);
		if ((r & 1) == 0)
			put(r--, -1);
	}
	pull(l_), pull(r_);
	purge(1);
}

int dojrzale(int l, int r) {
	return ft_query(r) - ft_query(l - 1);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10