rendered paste body#include <stdio.h>
#include <stdlib.h>
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 <assert.h>
#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;
}