oj.uz

Submission #948994

# Submission time Handle Problem Language Result Execution time Memory
948994 2024-03-18T18:31:19 Z rainboy Watering can (POI13_kon) C
100 / 100
 177 ms 22272 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5468 KB Output is correct
2 Correct 1 ms 5700 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 3 ms 5744 KB Output is correct
3 Correct 1 ms 5716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7632 KB Output is correct
2 Correct 23 ms 7248 KB Output is correct
3 Correct 23 ms 5540 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8468 KB Output is correct
2 Correct 38 ms 8364 KB Output is correct
3 Correct 37 ms 8240 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9556 KB Output is correct
2 Correct 42 ms 9552 KB Output is correct
3 Correct 54 ms 7796 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13104 KB Output is correct
2 Correct 63 ms 11568 KB Output is correct
3 Correct 91 ms 12180 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 13472 KB Output is correct
2 Correct 89 ms 14400 KB Output is correct
3 Correct 95 ms 12116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 18728 KB Output is correct
2 Correct 137 ms 16936 KB Output is correct
3 Correct 177 ms 19892 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 21584 KB Output is correct
2 Correct 149 ms 20892 KB Output is correct
3 Correct 169 ms 21844 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 21804 KB Output is correct
2 Correct 159 ms 22272 KB Output is correct
3 Correct 173 ms 21400 KB Output is correct