oj.uz

Submission #710793

# Submission time Handle Problem Language Result Execution time Memory
710793 2023-03-15T20:15:32 Z rainboy Selling RNA Strands (JOI16_selling_rna) C
100 / 100
 336 ms 22444 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5944 KB Output is correct
2 Correct 42 ms 8756 KB Output is correct
3 Correct 46 ms 8652 KB Output is correct
4 Correct 47 ms 8692 KB Output is correct
5 Correct 30 ms 5836 KB Output is correct
6 Correct 29 ms 5788 KB Output is correct
7 Correct 48 ms 8972 KB Output is correct
8 Correct 61 ms 10736 KB Output is correct
9 Correct 64 ms 10752 KB Output is correct
10 Correct 37 ms 8192 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8772 KB Output is correct
2 Correct 65 ms 5360 KB Output is correct
3 Correct 81 ms 6860 KB Output is correct
4 Correct 51 ms 5908 KB Output is correct
5 Correct 64 ms 5256 KB Output is correct
6 Correct 83 ms 7004 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 29 ms 5944 KB Output is correct
9 Correct 42 ms 8756 KB Output is correct
10 Correct 46 ms 8652 KB Output is correct
11 Correct 47 ms 8692 KB Output is correct
12 Correct 30 ms 5836 KB Output is correct
13 Correct 29 ms 5788 KB Output is correct
14 Correct 48 ms 8972 KB Output is correct
15 Correct 61 ms 10736 KB Output is correct
16 Correct 64 ms 10752 KB Output is correct
17 Correct 37 ms 8192 KB Output is correct
18 Correct 74 ms 8772 KB Output is correct
19 Correct 65 ms 5360 KB Output is correct
20 Correct 81 ms 6860 KB Output is correct
21 Correct 51 ms 5908 KB Output is correct
22 Correct 64 ms 5256 KB Output is correct
23 Correct 83 ms 7004 KB Output is correct
24 Correct 75 ms 10032 KB Output is correct
25 Correct 122 ms 11920 KB Output is correct
26 Correct 59 ms 9376 KB Output is correct
27 Correct 89 ms 10060 KB Output is correct
28 Correct 336 ms 22444 KB Output is correct
29 Correct 297 ms 19208 KB Output is correct