Submission #545130

#	Time	Username	Problem	Language	Result	Execution time	Memory
545130		rainboy	Tram (CEOI13_tram)	C11	100 / 100	32 ms	4884 KiB

tram

#include <stdio.h>
#include <string.h>

#define N	150000
#define M	30000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

long long dd[N + 2]; int hh[N + 2], iq[1 + N + 2], pq[N + 2], cnt;

int lt(int i, int j) {
	return dd[i] > dd[j] || dd[i] == dd[j] && hh[i] < hh[j];
}

int p2(int p) {
	return (p *= 2) > cnt ? 0 : p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p;
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}

int pq_first() { return iq[1]; }

void pq_remove(int i) {
	if (pq[i]) {
		int j = iq[cnt--];

		if (j != i)
			pq[j] = pq[i], pq_up(j), pq_dn(j);
		pq[i] = 0;
	}
}

int bb[N], n;

void add(int l, int r) {
	if (l == -1 || r == -1)
		return;
	if (l == n) {
		if (r == 0)
			return;
		if (r == n + 1)
			dd[l] = INF, hh[l] = 0 * 2 + 0;
		else if ((bb[r] & 1) == 0)
			dd[l] = (long long) r * r + 1, hh[l] = 0 * 2 + 0;
		else if ((bb[r] & 2) == 0)
			dd[l] = (long long) r * r + 1, hh[l] = 0 * 2 + 1;
		else
			dd[l] = (long long) r * r, hh[l] = 0 * 2 + 0;
	} else if (r == n + 1) {
		if (l == n - 1 && bb[l] == 3)
			return;
		if ((bb[l] & 1) == 0)
			dd[l] = (long long) (n - 1 - l) * (n - 1 - l) + 1, hh[l] = (n - 1) * 2 + 0;
		else if ((bb[l] & 2) == 0)
			dd[l] = (long long) (n - 1 - l) * (n - 1 - l) + 1, hh[l] = (n - 1) * 2 + 1;
		else
			dd[l] = (long long) (n - 1 - l) * (n - 1 - l), hh[l] = (n - 1) * 2 + 0;
	} else {
		int l_, r_, i, j, h;
		long long d_;

		if (l + 1 == r && bb[l] == 3)
			return;
		l_ = max((l + r) / 2 - 3, l), r_ = min((l + r) / 2 + 3, r - 1), d_ = -1, h = -1;
		for (i = l_; i <= r_; i++)
			for (j = 0; j < 2; j++) {
				long long d;

				d = INF;
				if ((bb[l] & 1) != 0)
					d = min(d, (long long) (l - i) * (l - i) + 0);
				if ((bb[l] & 2) != 0)
					d = min(d, (long long) (l - i) * (l - i) + 1);
				if ((bb[r] & 1) != 0)
					d = min(d, (long long) (r - i) * (r - i) + 0);
				if ((bb[r] & 2) != 0)
					d = min(d, (long long) (r - i) * (r - i) + 1);
				if (d_ < d)
					d_ = d, h = i * 2 + 0;
				d = INF;
				if ((bb[l] & 1) != 0)
					d = min(d, (long long) (l - i) * (l - i) + 1);
				if ((bb[l] & 2) != 0)
					d = min(d, (long long) (l - i) * (l - i) + 0);
				if ((bb[r] & 1) != 0)
					d = min(d, (long long) (r - i) * (r - i) + 1);
				if ((bb[r] & 2) != 0)
					d = min(d, (long long) (r - i) * (r - i) + 0);
				if (d_ < d)
					d_ = d, h = i * 2 + 1;
			}
		dd[l] = d_, hh[l] = h;
	}
	pq_add(l);
}

int main() {
	static int pp[N + 2], qq[N + 2], hh_[M];
	int m, k, g;

	scanf("%d%d", &n, &m);
	memset(pp, -1, (n + 2) * sizeof *pp);
	memset(qq, -1, (n + 2) * sizeof *qq);
	qq[n] = n + 1, pp[n + 1] = n;
	add(n, n + 1);
	k = 0;
	for (g = 0; g < m; g++) {
		static char s[2];
		int h, i, j;

		scanf("%s", s);
		if (s[0] == 'E') {
			int l, r;

			l = pq_first(), pq_remove(l), r = qq[l];
			hh_[g] = h = hh[l], i = h / 2, j = h % 2;
			printf("%d %d\n", i + 1, j + 1);
			if (i == l) {
				if (pp[l] != -1)
					pq_remove(pp[l]);
			} else {
				pp[i] = l, qq[i] = r;
				if (l != -1)
					qq[l] = i;
				if (r != -1)
					pp[r] = i;
			}
			bb[i] ^= 1 << j, add(pp[i], i), add(i, qq[i]);
		} else {
			int g_;

			scanf("%d", &g_), g_--;
			h = hh_[g_], i = h / 2, j = h % 2;
			if (pp[i] != -1)
				pq_remove(pp[i]);
			pq_remove(i);
			if ((bb[i] ^= (1 << j)) == 0) {
				if (pp[i] != -1)
					qq[pp[i]] = qq[i];
				if (qq[i] != -1)
					pp[qq[i]] = pp[i];
				add(pp[i], qq[i]);
			} else
				add(pp[i], i), add(i, qq[i]);
		}
	}
	return 0;
}

Compilation message (stderr)

tram.c: In function 'lt':
tram.c:14:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 |  return dd[i] > dd[j] || dd[i] == dd[j] && hh[i] < hh[j];
      |                          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
tram.c: In function 'main':
tram.c:119:9: warning: variable 'k' set but not used [-Wunused-but-set-variable]
  119 |  int m, k, g;
      |         ^
tram.c:121:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
tram.c:131:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
tram.c:152:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |    scanf("%d", &g_), g_--;
      |    ^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20