Submission #66046051

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Q_MAX 212345
int Q;
int T[Q_MAX];
char* S[Q_MAX];
char S_buf[512345];
struct node_s {
  int pos;
  struct node_s* next[26];
};
void ki_add(struct node_s** node, const char* str, int value) {
  if (*node == NULL) {
    *node = calloc(1, sizeof(**node));
    if (*node == NULL) exit(2);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define Q_MAX 212345

int Q;
int T[Q_MAX];
char* S[Q_MAX];

char S_buf[512345];

struct node_s {
	int pos;
	struct node_s* next[26];
};

void ki_add(struct node_s** node, const char* str, int value) {
	if (*node == NULL) {
		*node = calloc(1, sizeof(**node));
		if (*node == NULL) exit(2);
		(*node)->pos = Q + 1;
	}
	if (*str < 'a' || 'a' + 26 <= *str) {
		if ((*node)->pos > value) (*node)->pos = value;
	} else {
		ki_add(&(*node)->next[*str - 'a'], str + 1, value);
	}
}

int ki_get(const struct node_s* node, const char* str) {
	if (node == NULL) {
		return Q + 1;
	} else {
		int ans = node->pos;
		if ('a' <= *str && *str < 'a' + 26) {
			int candidate = ki_get(node->next[*str - 'a'], str + 1);
			if (candidate < ans) ans = candidate;
		}
		return ans;
	}
}

int bit_table[Q_MAX];

void bit_add(int pos, int value) {
	pos++;
	while (pos <= Q_MAX) {
		bit_table[pos - 1] += value;
		pos += pos & (-pos);
	}
}

int bit_sum(int pos) {
	int sum = 0;
	pos++;
	while (pos > 0) {
		sum += bit_table[pos - 1];
		pos -= pos & (-pos);
	}
	return sum;
}

int main(void) {
	int i;
	struct node_s* root = NULL;
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%512344s", &T[i], S_buf) != 2) return 1;
		S[i] = malloc(strlen(S_buf) + 1);
		if (S[i] == NULL) return 2;
		strcpy(S[i], S_buf);
	}
	/* X への追加を先に全て登録する */
	for (i = 0; i < Q; i++) {
		if (T[i] == 1) {
			ki_add(&root, S[i], i);
		}
	}
	/* 「どこで X に追加されるか」を管理し、それが現在かそれより前のものは引く */
	for (i = 0; i < Q; i++) {
		if (T[i]  == 2) {
			bit_add(ki_get(root, S[i]), 1);
		}
		printf("%d\n", bit_sum(Q + 10) - bit_sum(i));
	}
	return 0;
}

Submission Info

Judge Result