QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

# 21566. 四维偏序

统计

题目描述

在四维空间直角坐标系 $Oxyzw$ 中有 $n$ 个点 $P(x,y,z, w)$,你要统计有多少个点 $P_i, P_j$ 满足:

  • $x_i < x_j$

  • $y_i < y_j$

  • $z_i < z_j$

  • $w_i < w_j$

输入格式

输入的第一行包含一个整数 $n$。

接下来 $n$ 行,每行 $4$ 个整数 $x, y,z,w$,表示第 $i$ 个点的坐标为 $P_i(x, y, z, w)$

输出格式

输出一行一个整数,表示答案

样例数据

样例 1 输入

6
2 1 4 1
5 6 6 5 
3 3 3 4
6 4 5 6
4 5 2 3 
1 2 1 2

样例 1 输出

9

样例 2 输入

15
13 1 2 3
2 2 13 11
10 10 7 2
3 6 14 14
1 12 9 15
12 14 8 8
8 13 15 5
4 8 12 10
5 3 1 4
7 5 11 1
9 11 6 13
6 15 10 9
15 9 5 12
14 4 4 6
11 7 3 7

样例 2 输出

15

子任务

对于所有数据,保证 $x_i, y_i, z_i, w_i \in [1, n]$,没有两个点的任何一维坐标相同,$1 \leq n \leq 10^5$。