Submission #948914

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
948914	2024-03-18T16:25:00 Z	rainboy	Inspector (POI13_ins)	C	0 / 100	555 ms	35676 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], dd1[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(dd1, 0, (m_ + 1) * sizeof *dd1);
	c = 0;
	for (i = 0; i < n; i++)
		if (ll[i] <= rr[i])
			dd1[hh[ll[i]]]--, dd1[hh[rr[i]] + 1]++;
		else
			c++;
	d0 = d1 = 0;
	for (h = 0; h < m_; h++) {
		if (dd0[h] > 0)
			d0 += dd0[h];
		if (dd1[h] > 0)
			d1 += dd1[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 (dd1[h] < 0) {
			d = -dd1[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

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	348 KB	Output isn't correct
2	Incorrect	1 ms	460 KB	Output isn't correct
3	Incorrect	1 ms	348 KB	Output isn't correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Incorrect	3 ms	696 KB	Output isn't correct
6	Incorrect	6 ms	604 KB	Output isn't correct
7	Incorrect	12 ms	860 KB	Output isn't correct
8	Incorrect	47 ms	3144 KB	Output isn't correct
9	Incorrect	102 ms	6396 KB	Output isn't correct
10	Incorrect	205 ms	12880 KB	Output isn't correct
11	Incorrect	266 ms	17476 KB	Output isn't correct
12	Incorrect	555 ms	35676 KB	Output isn't correct
13	Incorrect	543 ms	34668 KB	Output isn't correct