BC.36.Gunner(hash) Gunner

 1 #include<stdio.h>
 2 #include<string.h>
 3 typedef long long ll ;
 4 const int M = 1000000 + 3 ;
 5 struct edge
 6 {
 7     int nxt ;
 8     ll num ;
 9 }e[M];
10 bool vis [M] ;
11 int H[M] , E ;
12 int cnt ;
13 int n , m  ;
14 ll h ;
15 
16 void init ()
17 {
18     E = 0 ;
19     memset (H , 0 , sizeof(H)) ;
20     memset (vis , 0 , sizeof(vis)) ;
21 }
22 
23 void Insert (ll x)
24 {
25     int y = x % M ;
26     if (y < 0) y += M ;
27     e[++ E].nxt = H[y] ;
28     e[E].num = x ;
29     H[y] = E ;
30 }
31 
32 bool Find (ll x)
33 {
34     int y = x % M ;
35     if (y < 0) y += M ;
36     for (int i = H[y] ; i ; i = e[i].nxt) {
37         if (e[i].num == x && vis[i]) {
38             return false ;
39         }
40         else if (e[i].num == x && !vis[i]) {
41             cnt ++ ;
42             vis[i] = true ;
43         }
44     }
45 }
46 
47 inline ll read () {
48     ll ans = 0; char c; bool flag = false;
49     while ((c = getchar()) == ' ' || c == '
' || c == '
');
50     if (c == '-') flag = true; else ans = c - '0';
51     while ((c = getchar()) >= '0' && c <= '9') ans = ans * 10 + c - '0';
52     return ans * (flag ? -1 : 1);
53 }
54 
55 int main ()
56 {
57    // freopen ("a.txt" , "r" , stdin ) ;
58     while (~ scanf ("%d%d" , &n , &m) ) {
59         init () ;
60         while (n--) {
61             h = read () ;
62             Insert (h) ;
63         }
64         while (m--) {
65             cnt = 0 ;
66             h = read () ;
67             Find (h) ;
68             printf ("%d
" , cnt) ;
69         }
70     }
71     return 0 ;
72 }