青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 74,  comments - 33,  trackbacks - 0

Beautiful People
The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength Si and beauty Bi. Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if Si <= Sj and Bi >= Bj or if Si >= Sj and Bi <= Bj (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn??t even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).

To celebrate a new 2005 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people who hate each other should be invited. On the other hand, to keep the club prestige at the apropriate level, administration wants to invite as many people as possible.

Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.


This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.


Input

The first line of the input file contains integer N - the number of members of the club. (2 <= N <= 100 000). Next N lines contain two numbers each - Si and Bi respectively (1 <= Si, Bi <= 109).


Output

On the first line of the output file print the maximum number of the people that can be invited to the party. On the second line output N integers - numbers of members to be invited in arbitrary order. If several solutions exist, output any one.


Sample Input

1

4
1 1
1 2
2 1
2 2


Sample Output

2
1 4


Author: Andrew Stankevich
很猥瑣的最長上升子序列,寫的很猥瑣 ,輸出為給出序列的序號,因為這個錯了幾次 開始的時候二分寫錯一直TLE
部分代碼如下

?

#include < cstdio >
#include
< cstring >
#include
< algorithm >
#define ?MAXN?120000
using ? namespace ?std;
struct ?NODE {
????
int ?x,y,mark;
}
arr[MAXN],num[MAXN];
bool ?OK;
int ?pre[MAXN],root[MAXN];
int ?n,top,max_sum,best_road;
int ?Search( int ?now) {
????
int ?left = 0 ,right = top,mid;
????
while (left < right) {
????????mid
= (right + left) >> 1 ;
????????
if (num[mid].y >= now)right = mid;
????????
else ?left = mid + 1 ;
????}

????mid
= (left + right) >> 1 ;
????
return ?mid;????
}

bool ?cmp(NODE?a,NODE?b) {
????
if (a.x != b.x) return ?a.x < b.x;
????
return ?a.y < b.y;????
}

void ?PRINT( int ?x) {
????
if (pre[x])PRINT(pre[x]);
????
if (OK)printf( " ? " );
????
else ?OK = true ;
????printf(
" %d " ,arr[x - 1 ].mark);
}

int ?main() {
????
int ?cases,i,j,now;
????scanf(
" %d " , & cases);
????num[
0 ].x = num[ 0 ].y = 0 ;
????
while (cases -- ) {
????????max_sum
= 0 ,top = 1 ;
????????scanf(
" %d " , & n);
????????
for (i = 0 ;i < n;i ++ ) {
????????????arr[i].mark
= i + 1 ;
????????????scanf(
" %d?%d " , & arr[i].x, & arr[i].y);????
????????}

????????sort(arr,arr
+ n,cmp);
????????memset(pre,
0 , sizeof (pre));
????????memset(num,
0 , sizeof (num));
????????
for (i = 0 ;i < n;i ++ ) {????
????????????
for (j = now;j < i + 1 ;j ++ ) {
????????????????
int ?t = Search(arr[j].y);
????????????????root[j]
= t;pre[j + 1 ] = num[t - 1 ].x;
????????????????
if (max_sum < t) {
????????????????????max_sum
= t;best_road = j + 1 ;????
????????????????}
????
????????????}

????????????
for (j = now;j < i + 1 ;j ++ ) {
????????????????
if (root[j] == top) {
????????????????????num[top].x
= j + 1 ;
????????????????????num[top
++ ].y = arr[j].y;????
????????????????}

????????????????
else ? if (arr[j].y < num[root[j]].y) {
????????????????????num[root[j]].x
= j + 1 ;
????????????????????num[root[j]].y
= arr[j].y;????
????????????????}
????
????????????}

????????}

????????OK
= false ;
????????printf(
" %d\n " ,max_sum);
????????PRINT(best_road);printf(
" \n " );
????}

}

posted on 2009-05-10 22:43 KNIGHT 閱讀(145) 評論(1)  編輯 收藏 引用

FeedBack:
# re: Beautiful People
2009-05-10 22:47 | Knignt
額 上面復制的時候搞錯了一句話 自己加到循環里面就可以了
從0到n的循環開始的時候加上
for(now=i,j=i+1;j<n&&arr[j].x==arr[i].x;i=j,j++);
用了二分的思想
  回復  更多評論
  
<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲综合国产| 亚洲天堂av在线免费观看| 久久久视频精品| 亚洲黄色免费网站| 亚洲国产日韩精品| 欧美精品三级日韩久久| 亚洲图片在区色| 亚洲男人第一av网站| 国产亚洲激情在线| 美日韩丰满少妇在线观看| 免费欧美视频| 香蕉久久a毛片| 久久人人爽人人爽爽久久| 夜夜嗨一区二区| 亚洲免费小视频| 亚洲丰满少妇videoshd| 99精品99久久久久久宅男| 国产亚洲精品aa午夜观看| 欧美激情aaaa| 国产精品一区二区在线观看| 欧美丰满少妇xxxbbb| 欧美系列精品| 欧美电影电视剧在线观看| 欧美视频一区二区在线观看 | 一区二区成人精品| 香蕉尹人综合在线观看| 最新69国产成人精品视频免费 | 久久久久国产精品一区| 欧美日韩激情小视频| 久久久久在线观看| 欧美婷婷久久| 欧美成人tv| 国产视频一区在线| 一本综合久久| 亚洲精品欧美日韩专区| 欧美一级艳片视频免费观看| 一道本一区二区| 免费观看日韩av| 久久免费黄色| 国产欧美日韩综合一区在线观看 | 亚洲视频碰碰| 99国产精品私拍| 玖玖在线精品| 久久久久久久久久久久久久一区| 欧美色播在线播放| 亚洲人体一区| 亚洲精品偷拍| 久久婷婷综合激情| 久久综合色婷婷| 国产亚洲观看| 午夜在线观看欧美| 性做久久久久久免费观看欧美| 欧美激情aaaa| 亚洲欧洲一区二区三区久久| 亚洲国产精品久久久久| 久久久久久久欧美精品| 久久婷婷蜜乳一本欲蜜臀| 国产欧美日韩免费看aⅴ视频| 亚洲伦理久久| 亚洲一二区在线| 欧美亚州一区二区三区| 99国内精品久久| 亚洲一区二区不卡免费| 欧美日韩一本到| 亚洲最新视频在线| 新67194成人永久网站| 国产精品一区二区视频| 亚洲综合三区| 久久久久久久综合色一本| 国产日韩欧美精品| 欧美在线综合视频| 男人的天堂亚洲在线| 亚洲精品欧洲精品| 欧美日韩一区二区欧美激情| 夜夜嗨一区二区三区| 欧美一区国产一区| 韩国一区二区三区美女美女秀| 久久久久久国产精品mv| 亚洲电影免费观看高清完整版| 日韩亚洲国产欧美| 欧美三级小说| 欧美在线观看网站| 欧美电影在线观看| 亚洲一区二区三区四区中文| 国产精品综合网站| 久久一日本道色综合久久| 亚洲国产精品久久久久久女王| 亚洲视频香蕉人妖| 国产专区综合网| 欧美精品久久99久久在免费线| 一区二区三区www| 久久久久国产一区二区三区| 亚洲人成在线播放网站岛国| 欧美日韩在线三级| 久久精品国产99| 亚洲精品久久久久| 久久国内精品视频| 亚洲美女精品久久| 国产欧美一区二区三区另类精品 | 久久视频一区二区| 亚洲在线视频| 国模私拍一区二区三区| 欧美日本一区二区视频在线观看| 亚洲免费中文| 亚洲免费av电影| 免费成人你懂的| 亚洲综合久久久久| 亚洲日本va午夜在线电影| 国产精品丝袜91| 欧美理论片在线观看| 久久精品五月| 亚洲欧美精品在线观看| 亚洲片在线观看| 久久综合九色综合欧美狠狠| 亚洲一区二区成人在线观看| 亚洲国内精品在线| 激情一区二区三区| 国产欧美日韩伦理| 欧美四级在线| 欧美精品在线观看一区二区| 欧美在线视频日韩| 亚洲免费一区二区| 一本色道**综合亚洲精品蜜桃冫 | 一区二区三区av| 亚洲国产欧美日韩精品| 麻豆视频一区二区| 久久国产精品亚洲77777| 亚洲一区二区三区在线观看视频| 亚洲人成亚洲人成在线观看| 国产在线拍揄自揄视频不卡99| 国产精品毛片a∨一区二区三区|国 | 欧美一区激情| 亚洲综合电影| 亚洲一区中文| 亚洲色在线视频| 夜夜精品视频| 亚洲一区在线免费观看| 亚洲欧美春色| 亚洲女ⅴideoshd黑人| 亚洲天堂男人| 亚洲欧美日韩精品一区二区 | 亚洲精品乱码久久久久| 日韩视频永久免费| 亚洲作爱视频| 制服丝袜亚洲播放| 亚洲伊人观看| 久久疯狂做爰流白浆xx| 欧美自拍丝袜亚洲| 久久深夜福利免费观看| 六月婷婷一区| 亚洲电影激情视频网站| 亚洲人成77777在线观看网| 亚洲精品在线三区| 亚洲深夜影院| 欧美在线free| 猫咪成人在线观看| 欧美日韩免费观看一区三区 | 另类激情亚洲| 欧美日本三级| 国产精品亚洲精品| 狠狠色噜噜狠狠色综合久| 亚洲高清在线观看一区| 中文欧美在线视频| 欧美一区免费视频| 欧美大秀在线观看| 一本色道久久综合亚洲精品不卡 | 欧美精品自拍| 国产麻豆日韩| 亚洲国语精品自产拍在线观看| 亚洲精品美女久久7777777| 亚洲婷婷在线| 久久青草福利网站| 999亚洲国产精| 久久高清国产| 欧美日韩精品综合| 黄色成人av在线| 亚洲图片激情小说| 免费欧美电影| 亚洲中字黄色| 欧美国产三区| 国产在线不卡视频| 这里只有精品视频| 久久综合狠狠综合久久综青草| 亚洲精选在线| 久久视频在线看| 国产精品免费网站在线观看| **网站欧美大片在线观看| 亚洲女同性videos| 亚洲承认在线| 亚洲一区二区三区四区五区黄 | 99一区二区| 久久伊人亚洲| 亚洲女人天堂成人av在线| 欧美xxx在线观看| 国产日韩欧美一区二区三区在线观看| 亚洲人成在线播放网站岛国| 久久九九免费| 亚洲欧美电影院| 欧美日韩在线不卡| 亚洲精品欧美日韩|