oj.uz

Submission #787977

# Submission time Handle Problem Language Result Execution time Memory
787977 2023-07-19T15:44:42 Z rainboy Gym Badges (NOI22_gymbadges) C
0 / 100
 358 ms 24324 KB 
#include <stdio.h>
#include <string.h>

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

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

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *vv;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (vv[ii[j]] == vv[i_])
				j++;
			else if (vv[ii[j]] < vv[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

long long ss[N_ * 2], dd[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	ss[i] = ss[l] + ss[r];
	dd[i] = min(dd[l], dd[r] == INF ? INF : dd[r] - ss[l]);
}

void build(int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	memset(dd + n_, 0x3f, n_ * sizeof *dd);
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int x, long long y) {
	i += n_;
	ss[i] = x, dd[i] = y;
	while (i > 1)
		pul(i >>= 1);
}

int main() {
	static int xx[N], yy[N], ii[N], idx[N];
	int n, h, i, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &xx[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &yy[i]);
	for (i = 0; i < n; i++)
		ii[i] = i;
	vv = yy, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		idx[ii[i]] = i;
	vv = xx, sort(ii, 0, n);
	build(n);
	k = 0;
	for (h = 0; h < n; h++) {
		i = ii[h];
		update(idx[i], xx[i], yy[i]);
		if (dd[1] >= 0)
			k++;
		else
			update(idx[i], 0, INF);
	}
	printf("%d\n", k);
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:68:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:70:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d", &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 24220 KB Output is correct
2 Correct 326 ms 24308 KB Output is correct
3 Correct 332 ms 24220 KB Output is correct
4 Correct 348 ms 24220 KB Output is correct
5 Correct 358 ms 24324 KB Output is correct
6 Correct 324 ms 24320 KB Output is correct
7 Correct 350 ms 24320 KB Output is correct
8 Correct 330 ms 24312 KB Output is correct
9 Correct 324 ms 24268 KB Output is correct
10 Correct 319 ms 24312 KB Output is correct
11 Correct 276 ms 24244 KB Output is correct
12 Correct 286 ms 24308 KB Output is correct
13 Correct 270 ms 24224 KB Output is correct
14 Correct 267 ms 24316 KB Output is correct
15 Incorrect 286 ms 24300 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -