oj.uz

Submission #882227

# Submission time Handle Problem Language Result Execution time Memory
882227 2023-12-02T20:16:37 Z rainboy Cambridge (info1cup18_cambridge) C
100 / 100
 62 ms 9968 KB 
#include <stdio.h>

#define N	100000
#define N_	(1 << 17)	/* 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 xx[N], yy[N];

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 (yy[ii[j]] == yy[i_])
				j++;
			else if (yy[ii[j]] < yy[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], st[N_ * 2]; int n_;

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

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

void build(int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		st[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, st[i] = y == INF ? INF : y - x;
	while (i > 1)
		pul(i >>= 1);
}

int main() {
	static int ii[N], idx[N], jj[N];
	int n, q, i, j;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]), yy[i]--;
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	for (i = 0; i < n; i++)
		idx[ii[i]] = i;
	build(n);
	for (i = 0, j = -1; i < n; i++) {
		while (j < n && st[1] >= 0) {
			j++;
			if (j == n)
				break;
			update(idx[j], xx[j], yy[j]);
		}
		jj[i] = j;
		update(idx[i], 0, INF);
	}
	while (q--) {
		scanf("%d%d", &i, &j), i--, j--;
		printf(j < jj[i] ? "1\n" : "0\n");
	}
	return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 46 ms 8092 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 5 ms 3164 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 8 ms 2908 KB Output is correct
4 Correct 16 ms 3420 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 46 ms 8092 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 5 ms 3164 KB Output is correct
6 Correct 8 ms 2908 KB Output is correct
7 Correct 16 ms 3420 KB Output is correct
8 Correct 62 ms 9480 KB Output is correct
9 Correct 62 ms 9480 KB Output is correct
10 Correct 61 ms 9368 KB Output is correct
11 Correct 53 ms 9968 KB Output is correct
12 Correct 50 ms 9348 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct