Submission #948919

#	Time	Username	Problem	Language	Result	Execution time	Memory
948919		rainboy	Inspector (POI13_ins)	C11	100 / 100	584 ms	3932 KiB

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 (stderr)

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 / 100