oj.uz

Submission #382601

# Submission time Handle Problem Language Result Execution time Memory
382601 2021-03-27T21:12:52 Z rainboy Strange Device (APIO19_strange_device) C
30 / 100
 1464 ms 106220 KB 
#include <stdio.h>

#define N	1000000

unsigned int X = 12345;

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

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

long long xx[N * 2], yy[N * 4], ll_[N * 2], rr_[N * 2];

int compare_x(int i, int j) {
	return xx[i] == xx[j] ? 0 : (xx[i] < xx[j] ? -1 : 1);
}

int compare_y(int i, int j) {
	return yy[i] == yy[j] ? 0 : (yy[i] < yy[j] ? -1 : 1);
}

int compare_l(int i, int j) {
	return ll_[i] == ll_[j] ? 0 : (ll_[i] < ll_[j] ? -1 : 1);
}

int (*compare)(int, int);

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) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				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;
	}
}

int main() {
	static long long ll[N], rr[N];
	static int ii_[N * 4], ii1[N * 2], kk[N * 2];
	int n, n_, n1, i, j, x, cnt;
	long long a, b, l, r, ans;

	scanf("%d%lld%lld", &n, &a, &b), a /= gcd(a, b + 1);
	for (i = 0; i < n; i++)
		scanf("%lld%lld", &ll[i], &rr[i]);
	n_ = 0, n1 = 0;
	for (i = 0; i < n; i++) {
		l = ll[i] / b, r = rr[i] / b;
		if (l == r)
			xx[n_] = l % a, yy[n_ << 1 | 0] = ll[i] % b, yy[n_ << 1 | 1] = rr[i] % b + 1, n_++;
		else {
			xx[n_] = l % a, yy[n_ << 1 | 0] = ll[i] % b, yy[n_ << 1 | 1] = b, n_++;
			xx[n_] = r % a, yy[n_ << 1 | 0] = 0, yy[n_ << 1 | 1] = rr[i] % b + 1, n_++;
			if (r - l > 1) {
				l++, r--;
				if (r - l + 1 >= a) {
					printf("%lld\n", a * b);
					return 0;
				}
				l %= a, r %= a;
				if (l <= r)
					ll_[n1] = l, rr_[n1] = r, n1++;
				else {
					ll_[n1] = l, rr_[n1] = a - 1, n1++;
					ll_[n1] = 0, rr_[n1] = r, n1++;
				}
			}
		}
	}
	for (i = 0; i < n_; i++)
		ii_[i] = i;
	compare = compare_x, sort(ii_, 0, n_);
	for (i = 0; i < n1; i++)
		ii1[i] = i;
	compare = compare_l, sort(ii1, 0, n1);
	ans = 0;
	for (i = 0, j = 0, r = -1, x = 0; i < n_; i++) {
		while (j < n1 && ll_[ii1[j]] <= xx[ii_[i]]) {
			int i1 = ii1[j++];

			if (r < ll_[i1])
				ans += rr_[i1] - ll_[i1] + 1, r = rr_[i1];
			else if (r < rr_[i1])
				ans += rr_[i1] - r, r = rr_[i1];
		}
		xx[ii_[i]] = r >= xx[ii_[i]] ? -1 : (i + 1 == n_ || xx[ii_[i + 1]] != xx[ii_[i]] ? x++ : x);
	}
	ans *= b;
	for (i = 0; i < n_ * 2; i++)
		ii_[i] = i;
	compare = compare_y, sort(ii_, 0, n_ * 2);
	cnt = 0;
	for (i = 0; i + 1 < n_ * 2; i++) {
		int i_ = ii_[i];

		x = xx[i_ >> 1];
		if ((i_ & 1) == 0) {
			if (x != -1 && kk[x]++ == 0)
				cnt++;
		} else {
			if (x != -1 && --kk[x] == 0)
				cnt--;
		}
		ans += (yy[ii_[i + 1]] - yy[ii_[i]]) * cnt;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

strange_device.c: In function 'main':
strange_device.c:59:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%d%lld%lld", &n, &a, &b), a /= gcd(a, b + 1);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.c:61:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%lld%lld", &ll[i], &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 496 ms 99332 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 627 ms 54564 KB Output is correct
3 Incorrect 1018 ms 106220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 627 ms 54564 KB Output is correct
3 Incorrect 1018 ms 106220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 627 ms 54564 KB Output is correct
3 Incorrect 1018 ms 106220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 78 ms 6508 KB Output is correct
3 Correct 93 ms 6336 KB Output is correct
4 Correct 1464 ms 63212 KB Output is correct
5 Correct 106 ms 7020 KB Output is correct
6 Correct 98 ms 6892 KB Output is correct
7 Correct 92 ms 6508 KB Output is correct
8 Correct 102 ms 7404 KB Output is correct
9 Correct 101 ms 7240 KB Output is correct
10 Correct 83 ms 6124 KB Output is correct
11 Correct 78 ms 6124 KB Output is correct
12 Correct 78 ms 6636 KB Output is correct
13 Correct 98 ms 7276 KB Output is correct
14 Correct 897 ms 49004 KB Output is correct
15 Correct 75 ms 6636 KB Output is correct
16 Correct 858 ms 48876 KB Output is correct
17 Correct 1099 ms 62188 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #8
0 / 30.0

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