oj.uz

Submission #787976

# Submission time Handle Problem Language Result Execution time Memory
787976 2023-07-19T15:41:34 Z rainboy Gym Badges (NOI22_gymbadges) C
0 / 100
 382 ms 33568 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 = 0; i < n; i++)
		dd[n_ + i] = INF;
	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:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:74:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d", &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Incorrect 1 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 340 ms 33536 KB Output is correct
2 Correct 344 ms 33536 KB Output is correct
3 Correct 382 ms 33492 KB Output is correct
4 Correct 360 ms 33536 KB Output is correct
5 Correct 351 ms 33568 KB Output is correct
6 Correct 325 ms 32584 KB Output is correct
7 Correct 340 ms 32084 KB Output is correct
8 Correct 324 ms 32476 KB Output is correct
9 Correct 327 ms 32532 KB Output is correct
10 Correct 339 ms 32580 KB Output is correct
11 Correct 287 ms 31468 KB Output is correct
12 Correct 279 ms 31596 KB Output is correct
13 Correct 270 ms 31592 KB Output is correct
14 Correct 278 ms 31604 KB Output is correct
15 Incorrect 269 ms 31604 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 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Incorrect 1 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 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -