#include #include typedef unsigned int uint; /* = hash = */ typedef struct { int key; uint value; } ht_entry_t; typedef struct { uint mask; uint fill; uint thres; ht_entry_t *table; } ht_t; static inline ht_t *ht_alloc(); static inline ht_t *ht_init(ht_t *ht); static inline ht_t *ht_free(ht_t *ht); static inline ht_t *ht_uninit(ht_t *ht); static inline ht_entry_t *ht_lookup(ht_t *ht, int key); static inline void ht_inc(ht_t *ht, int key); static inline uint ht_get(ht_t *ht, int key); static inline ht_t *ht_resize(ht_t *ht, uint hint); #define NDEBUG #include #define hash(x) x #define HT_MINSIZE 8 #define HT_MAXSIZE 1<<29 #define JUMP(i, j) i += j++ #define JUMP_FIRST(i, j) j = 1, i += j++ static inline void HT_CHECKFILL(ht_t *ht) { if (ht->fill >= ht->thres) { ht_resize(ht, ht->fill << 2); } } static inline ht_t *ht_alloc() { ht_t *ht = malloc(sizeof(ht_t)); assert(ht); return ht_init(ht); } static inline ht_t *ht_init(ht_t *ht) { ht->mask = 8 - 1; ht->thres = ((ht->mask + 1) * 3) >> 2; ht->fill = 0; ht->table = calloc(ht->mask + 1, sizeof(ht_entry_t)); assert(ht->table); return ht; } static inline ht_t *ht_uninit(ht_t *ht) { ht_entry_t *table = ht->table; ht->table = NULL; free(table); return ht; } static inline ht_t *ht_free(ht_t *ht) { ht_uninit(ht); free(ht); return NULL; } static inline ht_entry_t *ht_lookup(ht_t *ht, int key) { uint mask = ht->mask; uint i = hash(key); uint j; /* JUMP_QUAD, JUMP_PY */ ht_entry_t *table = ht->table; ht_entry_t *entry = table + (i & mask); assert(ht->table != NULL); if (entry->value == 0 || entry->key == key) { return entry; } assert(ht->fill <= ht->mask); for (JUMP_FIRST(i, j); ; JUMP(i, j)) { entry = table + (i & mask); if (entry->value == 0 || entry->key == key) { return entry; } } } static inline void ht_cleaninsert(ht_t *ht, int key, uint value) { uint mask = ht->mask; uint i = hash(key); uint j; ht_entry_t *table = ht->table; ht_entry_t *entry = table + (i & mask); if (entry->value) { for (JUMP_FIRST(i, j); entry->value; JUMP(i, j)) { entry = table + (i & mask); } } ++ht->fill; entry->key = key; entry->value = value; } static inline ht_t *ht_resize(ht_t *ht, uint hint) { uint newsize; uint oldfill = ht->fill; ht_entry_t *oldtable, *newtable, *entry; if (hint < oldfill << 1) { hint = oldfill << 1; } for (newsize = HT_MINSIZE; newsize < hint || newsize <= oldfill; newsize <<= 1) { assert(newsize < HT_MAXSIZE); } newtable = calloc(newsize, sizeof(ht_entry_t)); assert(newtable != NULL); oldtable = ht->table; ht->table = newtable; ht->mask = newsize-1; ht->thres = (3 * newsize) >> 2; ht->fill = 0; for (entry = oldtable; oldfill; ++entry) { if (entry->value) { --oldfill; ht_cleaninsert(ht, entry->key, entry->value); } } free(oldtable); return ht; } static inline uint ht_get(ht_t *ht, int key) { ht_entry_t *entry = ht_lookup(ht, key); return entry->value; } static inline void ht_inc(ht_t *ht, int key) { ht_entry_t *entry = ht_lookup(ht, key); if (entry->value) { ++entry->value; } else { ++ht->fill; entry->key = key; entry->value = 1; HT_CHECKFILL(ht); } } /* = sumfour = */ int *A; int *B; int *C; int *D; uint n; void readin() { char s[60]; char *p; uint i; fgets(s, 60, stdin); n = atoi(s); A = malloc(4 * n * sizeof(int)); B = A + n; C = B + n; D = C + n; for (i = 0; i < n; ++i) { fgets(s, 60, stdin); A[i] = strtol(s, &p, 10); B[i] = strtol(p, &p, 10); C[i] = strtol(p, &p, 10); D[i] = strtol(p, &p, 10); } } uint count() { uint i; uint j; uint s = 0; ht_t *ht; int a, c; ht = ht_resize(ht_alloc(), 6*n); i = n; while (i) { a = A[--i]; j = n; while (j) { ht_inc(ht, a + B[--j]); } } i = n; while (i) { c = -C[--i]; j = n; while (j) { s += ht_get(ht, c - D[--j]); } } // ht_free(ht); return s; } int main() { readin(); printf("%u\n", count()); // free(A); return 0; }