| 题目名称 | 2580. [HZOI 2015]偏序 II |
|---|---|
| 输入输出 | partial_order_two.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3500 ms (3.5 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Hzoi_
于2017-01-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：65， 提交：156， 通过率：41.67% | ||||
 GoatGirl98 |
100 | 3.183 s | 0.00 MiB | C++ |
 kito |
100 | 3.312 s | 7.65 MiB | C++ |
 ajcxsu |
100 | 5.530 s | 5.08 MiB | C++ |
 胡嘉兴 |
100 | 5.533 s | 8.72 MiB | C++ |
 HtBest |
100 | 5.936 s | 298.72 MiB | C++ |
|
梦那边的美好ET |
100 | 6.070 s | 298.82 MiB | C++ |
 fhr |
100 | 6.336 s | 13.14 MiB | C++ |
 MistyEye |
100 | 7.602 s | 10.31 MiB | C++ |
|
Go灬Fire |
100 | 7.757 s | 5.95 MiB | C++ |
|
哒哒哒哒哒！ |
100 | 7.930 s | 10.22 MiB | C++ |
| 关于 偏序 II 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @風掠過的瞬間一轉眼就不見 :
膜拜神犇的CDQ套CDQ套CDQ！O(nlog^4n) | ||||
 _Itachi
2017-01-19 14:19
4楼
| ||||
|
回复 @Mike is Fool :
$O(n \log ^4 n)$  AntiLeaf
2017-01-19 14:08
3楼
| ||||
|
前排膜拜meaty!
发现输入挂和快读实际差不了多少时间的说 | ||||
|
数据已完成，请审核
 Hzoi_
2017-01-07 07:11
1楼
| ||||
FoolMike2580. [HZOI 2015]偏序 II
★★★☆ 输入文件：partial_order_two.in
输出文件：partial_order_two.out
简单对比时间限制：3.5 s 内存限制：512 MiB
【题目描述】
给定一个有$n$个元素的序列，元素编号为$1$~$n$，每个元素有四个属性$a$,$b$,$c$,$d$，求序列中满足$i<j$且$a_i<a_j$且$b_i<b_j$且$c_i<c_j$且$d_i<d_j$的数对$(i,j)$的个数。
【输入格式】
第一行一个整数$n$，表示序列长度。
第二行$n$个整数，分别表示$a_1$~$a_n$。
第三行$n$个整数，分别表示$b_1$~$b_n$。
第四行$n$个整数，分别表示$c_1$~$c_n$。
第五行$n$个整数，分别表示$d_1$~$d_n$。
【输出格式】
一个整数，表示答案。
【样例输入】
5 1 4 5 2 3 3 5 2 1 4 2 3 4 1 5 2 3 1 5 4
【样例输出】
2
【样例解释】
满足条件的$(i,j)$共有以下2对：
$(1,2)$
$(1,5)$
【数据范围与约定】
对于30%的数据，$n$<=5000。
对于100%的数据，1<=$n$<=50000，保证所有的$a_i$、$b_i$、$c_i$、$d_i$分别组成四个$1$~$n$的排列。
请注意常数因子带来的程序效率上的影响。
【来源】
HZOI 2015