题目名称 2639. [HZOI 2015] 偏序++
输入输出 partial_order_plus.in/out
难度等级 ★★★☆
时间限制 4000 ms (4 s)
内存限制 512 MiB
测试数据 10 简单对比
题目来源 Gravatarkito 于2017-03-28加入
开放分组 全部用户
提交状态
分类标签
bitset K-D树
通过:117, 提交:249, 通过率:46.99%
Gravatarnow-ing 100 1.411 s 9.71 MiB C++
GravatarX_o_r 100 1.837 s 9.71 MiB C++
GravatarX_o_r 100 1.838 s 9.71 MiB C++
GravatarX_o_r 100 1.847 s 9.71 MiB C++
GravatarX_o_r 100 1.857 s 9.71 MiB C++
GravatarToocold 100 1.967 s 24.53 MiB C++
Gravatarnow-ing 100 2.177 s 24.53 MiB C++
Gravatarizlyforever 100 2.858 s 4.17 MiB C++
Gravatarizlyforever 100 2.868 s 4.21 MiB C++
Gravatarizlyforever 100 2.885 s 4.51 MiB C++
关于 偏序++ 的近10条评论(全部评论)
naive?我的Kd_tree也吊打了部分Bitset选手
Gravatarytxytx
2018-10-26 17:07 8楼
bitset吊打kdtree……
GravatarFoolMike
2017-03-30 21:12 7楼
bitset吊打kdtree……
GravatarFoolMike
2017-03-30 21:07 6楼
回复 @sxysxy :
快读没处理EOF显然会死循环然后就TLE了23333333
或者垃圾值太大/垃圾值不合法导致TLE
GravatarAlbert S. Chang
2017-03-28 21:28 5楼
震惊!没有freopen导致TLE
Gravatarsxysxy
2017-03-28 21:17 4楼
Gravatar哒哒哒哒哒!
2017-03-28 18:35 3楼
感觉我好慢。。
UPD:常数优化,效果拔群(其实我第一遍交的时候不知道count()这个函数,居然n^2统计答案)
Gravatar_Itachi
2017-03-28 17:47 2楼
前排
GravatarGo灬Fire
2017-03-28 17:08 1楼

2639. [HZOI 2015] 偏序++

★★★☆   输入文件:partial_order_plus.in   输出文件:partial_order_plus.out   简单对比
时间限制:4 s   内存限制:512 MiB

【题目描述】

给定一个有$n$个元素的序列,元素编号为$1$~$n$,每个元素有k个属性$p^1$,$p^2$,$p^3$,...,$p^k$,求序列中满足$i<j$且$1<=t<=k,p^t_i<p^t_j$的数对$(i,j)$的个数。

【输入格式】


第一行两个整数$n$,$k$,表示序列长度和属性个数。

接下来$k$行,每行$n$个整数,第$t$行表示$n$个元素的第$p^t$个属性。


【输出格式】

共1行,表示满足要求的数对个数。

【样例输入】

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

【样例输出】

2

【样例解释】

每个元素4个属性,满足要求的数对为(1,2),(1,5)。

【数据范围与约定】


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

另有40%的数据,1<=$n$<=40000,k=2。

对于100%的数据,1<=$n$<=40000,k<=6。保证对于所有元素的$p^t$属性组成一个$1$~$n$的排列。

请注意常数因子带来的程序效率上的影响。


【来源】

HZOI2015