Untitled
unknown
plain_text
a year ago
10 kB
11
Indexable
-----------------MAIN----------------------------------
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define CMD_INIT 1
#define CMD_ADD 2
#define CMD_REMOVE 3
#define CMD_NUMBER_OF_CROSS 4
#define CMD_PARTICIPANT 5
extern void init();
extern void add(int mX, int mY);
extern void remove(int mX, int mY);
extern int numberOfCross(int mID);
extern int participant(int mX, int mY);
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
static bool run()
{
int numQuery;
int mX, mY, mID;
int userAns, ans;
bool isCorrect = false;
scanf("%d", &numQuery);
for (int i = 0; i < numQuery; ++i)
{
int cmd;
scanf("%d", &cmd);
switch (cmd)
{
case CMD_INIT:
init();
isCorrect = true;
break;
case CMD_ADD:
scanf("%d %d", &mX, &mY);
add(mX, mY);
break;
case CMD_REMOVE:
scanf("%d %d", &mX, &mY);
remove(mX, mY);
break;
case CMD_NUMBER_OF_CROSS:
scanf("%d", &mID);
userAns = numberOfCross(mID);
scanf("%d", &ans);
if (userAns != ans)
{
isCorrect = false;
}
break;
case CMD_PARTICIPANT:
scanf("%d %d", &mX, &mY);
userAns = participant(mX, mY);
scanf("%d", &ans);
if (userAns != ans)
{
isCorrect = false;
}
break;
default:
isCorrect = false;
break;
}
}
return isCorrect;
}
int main()
{
setbuf(stdout, NULL);
freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++)
{
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
-----------------USER----------------------------------
#define rint register int
#define NULL 0
#define N 101
#define MY 1000000000
#define DUR 1000000
#define MAXNODE 410000
typedef struct Node{
int value, mx;
Node *next, *pre, *nei;
};
Node nodes[MAXNODE];
Node map[N][MY / DUR];
int nodeAllocIndex;
void InsertIntoMap(int x, Node* n)
{
int y_index = n->value / DUR;
Node *current = &map[x][y_index];
while (current->next != NULL && current->next->value > n->value)
current = current->next;
n->pre = current;
n->next = current->next;
if (current->next != NULL) current->next->pre = n;
current->next = n;
}
void RemoveFromMap(Node* n)
{
n->pre->next = n->next;
if (n->next != NULL) n->next->pre = n->pre;
}
Node* FindFromMap(int mx, int my)
{
int y_index = my / DUR;
Node* current = &map[mx][y_index];
while (current->next != NULL && current->next->value != my)
current = current->next;
return current->next;
}
Node* FindLowerBound(int mx, int my, int y_index)
{
Node* current = &map[mx][y_index];
while (current->next != NULL && current->next->value > my)
current = current->next;
return current->next;
}
Node* FindUpperBound(int mx, int my, int y_index)
{
Node* current = &map[mx][y_index];
while (current->next != NULL && current->next->value >= my)
current = current->next;
return current;
}
void init()
{
nodeAllocIndex = 0;
for (rint i = 1; i < N; i++)
{
for (rint j = 0; j < MY / DUR; j++)
{
map[i][j].value = -1;
map[i][j].next = NULL;
}
}
}
void add(int mX, int mY)
{
Node* n1 = &nodes[nodeAllocIndex++];
Node* n2 = &nodes[nodeAllocIndex++];
n1->nei = n2;
n1->value = mY;
n1->mx = mX;
InsertIntoMap(mX, n1);
n2->nei = n1;
n2->value = mY;
n2->mx = mX + 1;
InsertIntoMap(mX+1, n2);
}
void remove(int mX, int mY)
{
Node* n = FindFromMap(mX, mY);
RemoveFromMap(n);
RemoveFromMap(n->nei);
}
int numberOfCross(int mID)
{
int result = 0;
int x = mID, y = 0;
Node* n = NULL;
for (rint i = 0; i < MY / DUR; i++)
{
n = FindUpperBound(mID, i*DUR, i);
if (n->value != -1) break;
}
while (n->value != -1)
{
result++;
x = n->nei->mx, y = n->nei->value + 1;
for (rint i = y/DUR; i < MY / DUR; i++)
{
n = FindUpperBound(x, y, i);
if (n->value != -1) break;
}
}
return result;
}
int participant(int mX, int mY)
{
int x = mX, y = mY;
Node* n = NULL;
for (rint i = y/DUR; i >= 0; i--)
{
n = FindLowerBound(x, y, i);
if (n != NULL) break;
}
while (n != NULL)
{
x = n->nei->mx, y = n->nei->value-1;
for (rint i = y / DUR; i >= 0; i--)
{
n = FindLowerBound(x, y, i);
if (n != NULL) break;
}
}
return x;
}
--------------------INPUT---------------------------
25 100
11
1
5 5 7 5
2 4 1
5 5 7 4
2 5 5
5 5 7 6
2 5 3
5 5 7 4
3 4 1
5 5 7 5
4 5 2
13
1
2 1 3
4 1 1
4 1 1
5 3 3 3
3 1 3
2 1 7
5 2 5 2
2 3 5
2 1 9
2 2 2
4 4 1
5 1 3 1
13
1
2 5 2
2 4 9
4 7 0
4 5 1
4 2 0
5 5 7 6
5 10 1 10
2 3 1
2 1 4
5 5 8 6
2 3 5
3 1 4
20
1
2 4 8
2 3 5
3 3 5
2 4 6
3 4 8
2 4 9
5 3 10 3
4 14 0
4 9 0
2 7 10
5 8 8 8
2 9 7
5 6 12 6
5 11 13 11
4 11 0
2 1 1
4 1 1
5 4 7 5
4 8 1
261
1
2 5 78
5 52 51 52
4 34 0
5 9 7 9
5 28 53 28
4 13 0
4 74 0
4 58 0
4 22 0
4 11 0
4 9 0
4 18 0
5 17 56 17
2 92 93
4 76 0
4 46 0
4 38 0
2 92 96
5 75 54 75
4 12 0
5 34 25 34
4 41 0
4 11 0
4 51 0
5 31 31 31
2 49 99
4 10 0
4 55 0
5 22 36 22
2 15 77
5 56 15 56
2 66 44
5 42 17 42
5 36 62 36
5 37 30 37
2 90 9
5 83 53 83
5 59 31 59
5 9 96 9
5 15 85 16
4 63 0
4 95 0
5 53 89 53
2 42 72
4 76 0
2 24 25
4 8 0
5 28 1 28
5 99 61 99
5 86 13 86
5 67 20 67
5 25 45 24
5 72 46 72
5 23 28 23
5 84 65 84
5 45 72 45
2 49 37
4 53 0
5 47 50 47
5 26 26 26
4 54 0
4 69 0
5 22 94 22
4 45 0
4 67 1
4 45 0
3 49 99
4 84 0
4 39 0
4 84 0
5 38 99 38
5 24 99 25
2 47 49
3 66 44
4 9 0
5 96 19 96
5 11 80 11
2 66 91
5 89 12 89
5 9 71 9
5 66 19 66
4 51 0
4 62 0
5 34 9 34
5 89 76 89
5 13 59 13
2 52 39
5 16 89 15
2 99 68
4 76 0
4 72 0
4 93 2
4 6 1
4 57 0
2 30 32
2 65 43
2 44 30
2 31 34
5 95 92 95
5 24 24 24
5 92 70 92
2 33 7
5 76 14 76
2 70 41
2 9 33
5 32 7 32
2 36 70
4 43 1
5 51 74 51
2 16 40
4 14 0
4 37 1
4 94 0
5 81 94 81
3 52 39
4 61 0
5 32 52 30
5 12 3 12
2 34 55
2 86 52
4 61 0
5 81 83 81
2 41 90
5 98 1 98
5 53 60 53
4 64 0
2 93 14
2 54 80
2 46 19
5 6 90 5
5 45 93 44
2 91 67
4 91 1
5 56 10 56
4 79 0
5 69 98 69
4 79 0
2 11 45
3 86 52
5 100 50 100
4 99 1
2 51 8
4 34 1
5 15 76 15
4 7 0
5 93 28 94
5 74 23 74
4 77 0
4 84 0
4 79 0
2 69 94
4 18 0
4 1 0
4 11 1
4 13 0
4 8 0
2 89 65
4 21 0
5 55 44 55
5 57 4 57
5 17 96 16
2 22 63
3 99 68
5 74 1 74
2 56 17
4 11 1
5 54 48 54
5 4 49 4
3 11 45
4 73 0
4 64 0
5 11 53 11
4 61 0
5 38 86 38
4 40 0
5 13 94 13
4 31 1
4 1 0
5 52 36 51
5 58 26 58
5 30 19 30
4 13 0
5 14 65 14
5 51 3 51
4 33 2
3 56 17
2 88 74
5 44 26 44
4 43 2
4 21 0
5 17 84 16
5 68 47 68
4 51 1
5 89 49 89
5 83 18 83
4 85 0
2 13 85
4 33 2
4 19 0
2 50 62
5 12 32 12
2 85 47
4 30 2
5 38 19 38
4 50 1
4 74 0
3 51 8
5 27 11 27
4 63 0
5 44 40 45
4 20 0
2 4 73
2 58 28
2 80 12
5 66 27 66
4 6 1
4 55 1
4 96 0
5 5 89 6
2 23 57
4 6 1
5 97 29 97
5 50 74 51
4 53 0
2 33 2
4 63 0
4 19 0
4 8 0
5 83 50 83
3 42 72
4 10 1
4 81 1
3 23 57
5 58 58 59
2 59 24
4 49 2
5 40 68 40
4 8 0
4 99 0
2 79 60
4 13 1
4 72 0
4 97 0
4 38 0
5 71 56 70
5 24 45 25
5 31 87 32
2 2 21
5 78 33 78
2 59 36
4 45 1
5 39 54 39
5 24 5 24
5 4 90 5
2 99 59
4 39 0
5 86 46 86
5 45 96 44
4 90 4
5 10 35 9
261
1
2 47 22
5 96 20 96
4 16 0
5 28 75 28
2 59 96
2 65 87
2 89 41
4 84 0
5 60 43 60
2 51 51
5 37 77 37
5 2 48 2
4 62 0
4 39 0
2 38 67
4 26 0
5 50 87 50
5 29 73 29
5 38 87 39
4 95 0
5 55 61 55
5 71 72 71
4 31 0
5 15 18 15
5 71 42 71
5 5 76 5
3 38 67
5 64 8 64
5 18 53 18
5 47 85 48
5 73 30 73
2 27 72
4 51 1
5 9 8 9
2 97 84
4 9 0
5 76 68 76
4 42 0
2 40 98
5 96 17 96
4 37 0
5 69 81 69
4 43 0
4 99 0
2 5 62
5 6 77 5
5 8 7 8
5 77 17 77
5 53 3 53
5 51 65 52
4 71 0
4 40 1
5 45 72 45
3 89 41
5 74 59 74
5 75 69 75
5 1 63 1
4 80 0
5 5 63 6
4 74 0
5 34 19 34
4 52 1
3 47 22
5 15 82 15
2 89 70
5 10 15 10
4 60 1
4 92 0
5 96 89 96
4 32 0
5 74 76 74
4 68 0
4 63 0
5 99 4 99
4 83 0
4 96 0
5 14 74 14
2 13 6
5 90 48 90
4 43 0
5 91 33 91
2 56 16
4 96 0
5 92 56 92
5 19 45 19
5 8 4 8
4 57 1
2 42 60
4 10 0
4 95 0
5 40 60 40
5 66 10 66
3 13 6
5 84 42 84
4 35 0
4 11 0
2 70 37
4 78 0
2 35 17
4 52 1
2 20 39
4 7 0
4 19 0
5 28 68 28
5 32 54 32
5 72 16 72
4 12 0
4 71 1
4 40 1
5 92 100 92
4 88 0
4 43 1
4 51 1
4 38 0
4 34 0
4 39 0
5 92 95 92
4 35 1
5 92 89 92
2 21 91
3 89 70
2 55 78
4 20 2
5 2 11 2
2 87 80
5 10 92 10
4 91 0
2 11 34
4 23 0
2 21 65
4 25 0
5 44 38 44
5 99 31 99
4 75 0
3 87 80
5 98 85 97
2 2 50
2 8 66
3 40 98
4 56 1
5 10 15 10
5 66 83 66
4 92 0
5 24 72 24
5 47 34 47
4 10 0
5 66 82 66
5 16 52 16
3 51 51
5 49 35 49
4 100 0
4 50 0
4 67 0
5 24 28 24
5 78 6 78
2 24 59
4 58 0
4 32 0
4 35 1
5 20 64 21
5 14 48 14
4 63 0
2 30 83
2 49 93
4 52 0
4 80 0
4 28 1
4 11 1
5 37 89 37
4 56 1
2 88 28
5 78 100 78
2 10 48
4 98 1
5 9 18 9
2 4 21
2 51 15
4 23 0
4 76 0
5 19 77 19
5 3 49 3
4 32 0
5 11 18 11
5 33 63 33
2 47 10
4 62 0
5 87 29 87
2 59 99
5 62 19 62
2 68 14
4 52 1
2 55 36
4 53 0
4 26 0
2 70 32
2 42 26
4 57 3
4 19 0
5 57 91 56
4 25 1
4 82 0
4 21 1
5 4 14 4
2 31 33
5 73 42 73
2 13 64
5 11 5 11
2 11 90
4 53 0
5 26 7 26
2 79 69
4 82 0
2 93 3
4 3 1
4 76 0
5 70 28 70
5 55 40 57
4 70 2
2 12 35
4 97 1
4 98 1
4 29 0
3 27 72
4 8 1
4 80 1
4 98 1
5 26 15 26
5 83 11 83
4 19 0
5 47 19 48
4 34 0
4 99 0
5 74 17 74
2 88 88
5 52 67 51
5 12 9 12
4 40 0
4 55 2
2 77 81
4 7 0
2 42 5
5 48 2 48
2 56 27
3 79 69
2 75 25
2 13 20
5 71 2 71
2 72 24
5 9 12 9
5 98 76 98
5 88 82 89
5 76 13 76
4 94 1
5 51 21 52
4 51 1
4 53 0
5 44 40 44
5 89 97 89
4 34 0
5 45 75 45