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

ins

#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]++;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	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