题目名称 2479. [HZOI 2016] 偏序
输入输出 partial_order.in/out
难度等级 ★★★☆
时间限制 2500 ms (2.5 s)
内存限制 512 MB
测试数据 10 简单对比
题目来源 2016-10-08
开放分组 全部用户
提交状态
分类标签
陈丹琦分治 树套树 K-D树 bitset
通过:117, 提交:409, 通过率:28.61%
Gravatarlitble 100 1.246 s C++
Gravatarajcxsu 100 1.257 s C++
Gravatarscy_666 100 1.264 s C++
Gravatareniac 100 1.266 s C++
Gravatarquhengyi11 100 1.303 s C++
Gravatarquhengyi11 100 1.305 s C++
Gravatarguodx 100 1.320 s C++
Gravatarbaodream 100 1.341 s C++
GravatarAntiLeaf 100 1.346 s C++
Gravatarbaodream 100 1.346 s C++
关于 偏序 的讨论
感觉自己好丧病......
标程最坏情况跑了1.3s,时间就开成2.5s好了
评测机心情不好啊......刚才闲来无事交一遍就T了,上午可是怎么重评都不会T的啊QAQ
GravatarHzoi_
2016-10-08 18:56 1楼
回复 @Hzoi_hzoier :
%%%
Gravatar沉迷学习的假的Keller
2016-10-06 17:04 2楼
回复 @Ezoi_HelenKeller :
%%%
GravatarAntiLeaf
2016-10-06 17:30 3楼
最近愈发zz了啊啊啊啊
时间复杂度一开始以为是nlogn^4还在想为什么理论上暴力比正解更优
但还是想不通空间复杂度啊,不应该是nlogn么,为什么我的内存池开到100W会RE啊@Hzoi_hzoier
Gravatar喵喵喵
2016-10-13 16:02 4楼
回复 @多冷的隆冬哒哒~ :
并不清楚
你写的哪种平衡树
GravatarAntiLeaf
2016-10-13 16:14 5楼
回复 @Hzoi_AntiLeaf :
我写的treap啊
Gravatar喵喵喵
2016-10-13 16:43 6楼
回复 @多冷的隆冬哒哒~ :
好吧这种玄学问题我也不明白了
= =反正开大点死不了
GravatarAntiLeaf
2016-10-13 19:09 7楼
CDQ套树套树写得要死了....
Gravatarsxysxy
2016-12-09 19:46 8楼
kd树大法好,直接无视内存,但时间是硬伤
GravatarFoolMike
2016-12-21 11:18 9楼
终于get了CDQ套CDQ= =
GravatarAntiLeaf
2016-12-21 15:53 10楼
(我是不会说 折半bitset可以卡时+卡空间过的)
GravatarSiriusRen
2017-01-22 00:24 11楼
Gravatar喵喵喵
2017-07-12 18:26 12楼
平衡树居然暴力清零了。。。。
Gravatarxzz_666
2017-10-23 07:46 13楼

2479. [HZOI 2016] 偏序

★★★☆   输入文件:partial_order.in   输出文件:partial_order.out   简单对比
时间限制:2.5 s   内存限制:512 MB

【题目描述】

给定一个有$n$个元素的序列,元素编号为$1$~$n$,每个元素有三个属性$a$,$b$,$c$,求序列中满足$i<j$且$a_i<a_j$且$b_i<b_j$且$c_i<c_j$的数对$(i,j)$的个数。

【输入格式】

第一行一个整数$n$,表示序列长度。

第二行$n$个整数,分别表示$a_1$~$a_n$。

第三行$n$个整数,分别表示$b_1$~$b_n$。

第四行$n$个整数,分别表示$c_1$~$c_n$。

【输出格式】

一个整数,表示答案。

【样例输入】

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

【样例输出】

3

【样例解释】

满足条件的$(i,j)$共有以下三对:

$(1,2)$

$(1,3)$

$(1,4)$

【数据范围与约定】

对于30%的数据,$n$<=5000。

对于100%的数据,1<=$n$<=50000,保证所有的$a_i$、$b_i$、$c_i$分别组成三个$1$~$n$的排列。

【来源】

HZOI 2016