제출 #710793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710793		rainboy	Selling RNA Strands (JOI16_selling_rna)	C11	100 / 100	336 ms	22444 KiB

selling_rna

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

#define N	100000
#define M	100000
#define N_	(N + M * 4)
#define L	100000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

void reverse(char *s, int l) {
	int i, j;
	char tmp;

	for (i = 0, j = l - 1; i < j; i++, j--)
		tmp = s[i], s[i] = s[j], s[j] = tmp;
}

char *ss[N], *tt[N]; int xx[N + M * 4], yy[N + M * 4], n, m;

int compare_s(int i, int j) {
	return strcmp(ss[i], ss[j]);
}

int compare_t(int i, int j) {
	return strcmp(tt[i], tt[j]);
}

int compare_xy(int i, int j) {
	return xx[i] != xx[j] ? xx[i] - xx[j] : yy[j] - yy[i];
}

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int search(char **ss, int *ii, char *s, int n, int l, int incl) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2;
		int c = strncmp(ss[ii[i]], s, l);

		if (c < 0 || c == 0 && incl)
			lower = i;
		else
			upper = i;
	}
	return upper;
}

int ft[N];

void update(int i, int n) {
	while (i < n) {
		ft[i]++;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int ii[N], jj[N], hh[N + M * 4], ans[M];
	int l, h, h_, i, j;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		static char s[L + 1];

		scanf("%s", s), l = strlen(s);
		ss[i] = strdup(s);
		reverse(s, l);
		tt[i] = strdup(s);
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_s, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		xx[ii[i]] = i;
	for (j = 0; j < n; j++)
		jj[j] = j;
	compare = compare_t, sort(jj, 0, n);
	for (j = 0; j < n; j++)
		yy[jj[j]] = j;
	for (h = 0; h < m; h++) {
		static char pp[L + 1], qq[L + 1];
		int l, x1, x2, y1, y2;

		scanf("%s%s", pp, qq);
		l = strlen(pp);
		x1 = search(ss, ii, pp, n, l, 0);
		x2 = search(ss, ii, pp, n, l, 1);
		l = strlen(qq), reverse(qq, l);
		y1 = search(tt, jj, qq, n, l, 0);
		y2 = search(tt, jj, qq, n, l, 1);
		xx[n + (h << 2 | 0)] = x1, yy[n + (h << 2 | 0)] = y1;
		xx[n + (h << 2 | 1)] = x1, yy[n + (h << 2 | 1)] = y2;
		xx[n + (h << 2 | 2)] = x2, yy[n + (h << 2 | 2)] = y1;
		xx[n + (h << 2 | 3)] = x2, yy[n + (h << 2 | 3)] = y2;
	}
	for (h = 0; h < n + m * 4; h++)
		hh[h] = h;
	compare = compare_xy, sort(hh, 0, n + m * 4);
	for (h = 0; h < n + m * 4; h++) {
		h_ = hh[h];
		if (h_ < n)
			update(yy[h_], n);
		else
			ans[h_ - n >> 2] += query(yy[h_] - 1) * ((h_ - n & 3) == 0 || (h_ - n & 3) == 3 ? 1 : -1);
	}
	for (h = 0; h < m; h++)
		printf("%d\n", ans[h]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.c: In function 'search':
selling_rna.c:68:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |   if (c < 0 || c == 0 && incl)
      |                ~~~~~~~^~~~~~~
selling_rna.c: In function 'main':
selling_rna.c:142:11: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  142 |    ans[h_ - n >> 2] += query(yy[h_] - 1) * ((h_ - n & 3) == 0 || (h_ - n & 3) == 3 ? 1 : -1);
      |        ~~~^~~
selling_rna.c:142:49: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  142 |    ans[h_ - n >> 2] += query(yy[h_] - 1) * ((h_ - n & 3) == 0 || (h_ - n & 3) == 3 ? 1 : -1);
      |                                              ~~~^~~
selling_rna.c:142:70: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  142 |    ans[h_ - n >> 2] += query(yy[h_] - 1) * ((h_ - n & 3) == 0 || (h_ - n & 3) == 3 ? 1 : -1);
      |                                                                   ~~~^~~
selling_rna.c:99:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
selling_rna.c:103:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%s", s), l = strlen(s);
      |   ^~~~~~~~~~~~~~
selling_rna.c:122:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |   scanf("%s%s", pp, qq);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40