Submission #948919

# Submission time Handle Problem Language Result Execution time Memory
948919 2024-03-18T16:29:47 Z rainboy Inspector (POI13_ins) C
100 / 100
584 ms 3932 KB
#include <stdio.h>
#include <string.h>

#define N	100000
#define M	100000

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

int solve(int *tt, int *ii, int *cc, int n, int m, int k) {
	static int ll[N], rr[N], hh[M], dd0[M + 1], dd1p[M + 1], dd1n[M + 1];
	int m_, h, i, t, c, d, d0, d1;

	memset(dd0, 0, m * sizeof *dd0);
	for (i = 0; i < n; i++)
		ll[i] = m, rr[i] = -1;
	for (h = 0; h < k; h++) {
		i = ii[h], t = tt[h];
		ll[i] = min(ll[i], t), rr[i] = max(rr[i], t);
		if (dd0[t] == 0)
			dd0[t] = cc[h];
		else if (dd0[t] != cc[h])
			return 0;
	}
	m_ = 0;
	for (t = 0; t < m; t++)
		if (dd0[t] != 0)
			dd0[hh[t] = m_++] = dd0[t];
	dd0[m_] = 0;
	for (h = m_; h > 0; h--)
		dd0[h] -= dd0[h - 1];
	memset(dd1p, 0, (m_ + 1) * sizeof *dd1p);
	memset(dd1n, 0, (m_ + 1) * sizeof *dd1n);
	c = 0;
	for (i = 0; i < n; i++)
		if (ll[i] <= rr[i])
			dd1n[hh[ll[i]]]++, dd1p[hh[rr[i]] + 1]++;
		else
			c++;
	d0 = d1 = 0;
	for (h = 0; h <= m_; h++) {
		if (dd0[h] > 0)
			d0 += dd0[h];
		d1 += dd1p[h];
		if (dd0[h] < 0) {
			d = -dd0[h];
			if (d <= d1)
				d1 -= d;
			else {
				d -= d1, d1 = 0;
				if (d > d0 || d > c)
					return 0;
				d0 -= d, c -= d;
			}
		}
		if (dd1n[h] > 0) {
			d = dd1n[h];
			if (d <= d0)
				d0 -= d;
			else {
				d -= d0, d0 = 0;
				if (d > d1)
					return 0;
				d1 -= d;
			}
		}
	}
	return 1;
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int tt[M], ii[M], cc[M];
		int n, m, k, h, lower, upper;

		scanf("%d%d", &n, &m);
		for (h = 0; h < m; h++)
			scanf("%d%d%d", &tt[h], &ii[h], &cc[h]), tt[h]--, ii[h]--, cc[h]++;
		lower = 0, upper = m + 1;
		while (upper - lower > 1) {
			k = (lower + upper) / 2;
			if (solve(tt, ii, cc, n, m, k))
				lower = k;
			else
				upper = k;
		}
		printf("%d\n", lower);
	}
	return 0;
}

Compilation message

ins.c: In function 'main':
ins.c:74:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
ins.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d", &n, &m);
      |   ^~~~~~~~~~~~~~~~~~~~~
ins.c:81:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |    scanf("%d%d%d", &tt[h], &ii[h], &cc[h]), tt[h]--, ii[h]--, cc[h]++;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 3 ms 2484 KB Output is correct
6 Correct 5 ms 2396 KB Output is correct
7 Correct 9 ms 2396 KB Output is correct
8 Correct 46 ms 2396 KB Output is correct
9 Correct 104 ms 2712 KB Output is correct
10 Correct 201 ms 2904 KB Output is correct
11 Correct 278 ms 3160 KB Output is correct
12 Correct 584 ms 3920 KB Output is correct
13 Correct 539 ms 3932 KB Output is correct