Submission #774368

#	Time	Username	Problem	Language	Result	Execution time	Memory
774368		rainboy	Double Attendance (CCO22_day1problem3)	C11	25 / 25	286 ms	20244 KiB

Main

#include <stdio.h>

#define N1	300000
#define N2	300000
#define INF	0x7fffffff

int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

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

int *xx;

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 (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[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;
	}
}

void read(int *ll, int *rr, int n) {
	static int ii[N1], ll_[N1], rr_[N1];
	int i;

	for (i = 0; i < n; i++) {
		scanf("%d%d", &ll[i], &rr[i]);
		ii[i] = i;
	}
	xx = ll, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		ll_[i] = ll[ii[i]], rr_[i] = rr[ii[i]];
	for (i = 0; i < n; i++)
		ll[i] = ll_[i], rr[i] = rr_[i];
	ll[n] = rr[n] = INF;
}

int search(int *ll, int *rr, int n, int x, int *j_, int *x_) {
	int lower, upper;

	lower = -1, upper = n;
	while (upper - lower > 1) {
		int i = (lower + upper) / 2;

		if (ll[i] <= x)
			lower = i;
		else
			upper = i;
	}
	if (lower == -1 || rr[lower] <= x)
		*j_ = lower + 1, *x_ = ll[lower + 1];
	else
		*j_ = lower, *x_ = x;
	return lower;
}

int main() {
	static int ll1[N1 + 1], rr1[N1 + 1], ll2[N2 + 1], rr2[N2 + 1];
	int n1, n2, d, i1, j1, x1, i2, j2, x2, i1_, j1_, x1_, i2_, j2_, x2_, k;

	scanf("%d%d%d", &n1, &n2, &d);
	read(ll1, rr1, n1);
	read(ll2, rr2, n2);
	i1 = -1, search(ll1, rr1, n1, 0, &j1, &x1);
	i2 = -1, search(ll2, rr2, n2, d, &j2, &x2);
	k = 1;
	while (1) {
		if (x1 == INF) {
			i1_ = j2, search(ll1, rr1, n1, max(x2 + d, ll1[i2 + 1]), &j1_, &x1_);
			i2_ = i2, j2_ = j2 + 1, x2_ = ll2[j2 + 1];
		} else if (x2 == INF) {
			i1_ = i1, j1_ = j1 + 1, x1_ = ll1[j1 + 1];
			i2_ = j1, search(ll2, rr2, n2, max(x1 + d, ll2[i1 + 1]), &j2_, &x2_);
		} else {
			i1_ = j2, search(ll1, rr1, n1, max(x2 + d, ll1[i2 + 1]), &j1_, &x1_);
			if (i1_ >= i1 && j1_ >= j1 + 1)
				i1_ = i1, j1_ = j1 + 1, x1_ = ll1[j1 + 1];
			i2_ = j1, search(ll2, rr2, n2, max(x1 + d, ll2[i1 + 1]), &j2_, &x2_);
			if (i2_ >= i2 && j2_ >= j2 + 1)
				i2_ = i2, j2_ = j2 + 1, x2_ = ll2[j2 + 1];
		}
		i1 = i1_, j1 = j1_, x1 = x1_, i2 = i2_, j2 = j2_, x2 = x2_;
		if (x1 == INF && x2 == INF)
			break;
		k++;
	}
	printf("%d\n", k);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'read':
Main.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d", &ll[i], &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c: In function 'main':
Main.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d%d", &n1, &n2, &d);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 6 / 6
• Subtask 4: 4 / 4