-
Notifications
You must be signed in to change notification settings - Fork 1
/
P2161.c
114 lines (105 loc) · 2.21 KB
/
P2161.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include "stdio.h"
#include "stdlib.h"
int tree_size;
int removed_node_num;
typedef struct TNode {
int start, end;
struct TNode * left;
struct TNode * right;
} * Tree;
Tree newTNode(int start, int end) {
Tree t = (Tree)malloc(sizeof(struct TNode));
t->start = start;
t->end = end;
t->left = t->right = NULL;
return t;
}
Tree insert(Tree tree, int start, int end);
Tree leftOverlap(Tree tree, int start);
Tree rightOverlap(Tree tree, int end);
void deleteTree(Tree tree);
Tree insert(Tree tree, int start, int end) {
if (tree == NULL) {
tree_size++;
return newTNode(start, end);
}
if (end < tree->start) {
tree->left = insert(tree->left, start, end);
}
else if (start > tree->end) {
tree->right = insert(tree->right, start, end);
}
else {
if (start < tree->start) {
tree->left = leftOverlap(tree->left, start);
}
if (end > tree->end) {
tree->right = rightOverlap(tree->right, end);
}
tree->start = start;
tree->end = end;
removed_node_num++;
}
return tree;
}
Tree leftOverlap(Tree tree, int start) {
if (tree == NULL) return NULL;
if (tree->end < start) {
tree->right = leftOverlap(tree->right, start);
return tree;
}
else {
deleteTree(tree->right);
tree->right = NULL;
Tree left = tree->left;
free(tree);
removed_node_num++;
tree_size--;
return leftOverlap(left, start);
}
}
Tree rightOverlap(Tree tree, int end) {
if (tree == NULL) return NULL;
if (tree->start > end) {
tree->left = rightOverlap(tree->left, end);
return tree;
}
else {
deleteTree(tree->left);
tree->left = NULL;
Tree right = tree->right;
free(tree);
removed_node_num++;
tree_size--;
return rightOverlap(right, end);
}
}
void deleteTree(Tree tree) {
if (tree == NULL) return;
if (tree->left) deleteTree(tree->left);
if (tree->right) deleteTree(tree->right);
free(tree);
removed_node_num++;
tree_size--;
}
int main() {
Tree tree = NULL;
tree_size = 0;
int n ,start, end;
scanf("%d", &n);
char cmd;
for (int i = 0; i < n; i++) {
scanf(" %c", &cmd);
if (cmd == 'A') {
scanf("%d %d", &start, &end);
removed_node_num = 0;
tree = insert(tree, start, end);
printf("%d\n", removed_node_num);
}
else {
printf("%d\n", tree_size);
}
}
deleteTree(tree);
return 0;
}