coreBugZJ

此 blog 已棄。

POJ 2528 Mayor's posters

/*
2

POJ 2528 Mayor's posters
3

----問題描述：
6

The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim.
8

The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
9

Every candidate can place exactly one poster on the wall.
10

All posters are of the same height equal to the height of the wall;
11

the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
12

The wall is divided into segments and the width of each segment is one byte.
13

Each poster must completely cover a contiguous number of wall segments.
14

They have built a wall 10000000 bytes long (such that there is enough place for all candidates).
16

When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width.
17

Moreover, the candidates started placing their posters on wall segments already occupied by other posters.
18

Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
19

Your task is to find the number of visible posters when all the posters are placed given the information about posters' size,
20

their place and order of placement on the electoral wall.
21

----輸入：
24

The first line of input contains a number c giving the number of cases that follow.
26

The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,

, ri.
27

----輸出：
30

For each input data set print the number of visible posters after all the posters are placed.
32

----樣例輸入：
35

1
37

5
38

1 4
39

2 6
40

8 10
41

3 4
42

7 10
43

----樣例輸出：
46

4
48

----分析：
51

線段樹。
53

*/
56

#include <iostream>
60

#include <algorithm>
61

using namespace std;
63

template<unsigned int N>
65

class CSegTree
66

{
67

public :
68

void init( int b, int e ){
69

init( 1, b, e );
70

}
71

void modify( int b, int e, int d ){
72

begin = b;
73

end = e;
74

data = d;
75

modify( 1 );
76

}
77

int query( void ){
78

memset( visible, 0, sizeof( visible ) );
79

query( 1 );
80

data = 0;
81

for( int i = 1; i < N; ++i ){
82

if( visible[ i ] ){
83

++data;
84

}
85

}
86

return data;
87

}
88

private :
90

void init( int node, int b, int e ){
91

left[ node ] = b;
92

right[ node ] = e;
93

id[ node ] = 0;
94

if( b < e ){
95

init( node << 1, b, ( b + e ) >> 1 );
96

init( ( node << 1 ) + 1, ( ( b + e ) >> 1 ) + 1, e );
97

}
98

}
99

void modify( int node ){
100

if( ( end < left[ node ] ) || ( right[ node ] < begin ) ){
101

return;
102

}
103

if( data == id[ node ] ){
104

return;
105

}
106

if( ( begin <= left[ node ] ) && ( right[ node ] <= end ) ){
107

id[ node ] = data;
108

return;
109

}
110

if( id[ node ] ){
111

id[ node << 1 ] = id[ ( node << 1 ) + 1 ] = id[ node ];
112

id[ node ] = 0;
113

}
114

modify( node << 1 );
115

modify( ( node << 1 ) + 1 );
116

if( id[ node << 1 ] == id[ ( node << 1 ) + 1 ] ){
117

id[ node ] = id[ node << 1 ];
118

}
119

}
120

void query( int node ){
121

if( id[ node ] ){
122

visible[ id[ node ] ] = true;
123

return;
124

}
125

if( left[ node ] >= right[ node ] ){
126

return;
127

}
128

query( node << 1 );
129

query( ( node << 1 ) + 1 );
130

}
131

132

enum{ L = N * 3 };
133

typedef int IA[ L ];
134

IA left, right, id;
135

bool visible[ N ];
136

137

int begin, end, data;
138

139

};
140

141

template<unsigned int N, unsigned int NT>
142

class CLine
143

{
144

public :
145

friend istream & operator>>( istream & is, CLine<N,NT> & li ){
146

is >> li.n;
147

for( int i = 1; i <= li.n; ++i ){
148

is >> li.left[ i ] >> li.right[ i ];
149

}
150

return is;
151

}
152

void init_tree( CSegTree<NT> & tree ){
153

int i, j;
154

n2 = n << 1;
155

for( j = i = 1; i <= n; ++i,++j ){
156

line[ j ].p = left[ i ];
157

line[ j ].id = i;
158

line[ j ].bLeft = true;
159

160

++j;
161

line[ j ].p = right[ i ];
162

line[ j ].id = i;
163

line[ j ].bLeft = false;
164

}
165

sort( line + 1, line + n2 + 1 );
166

tp = 0;
167

line[ 0 ].p = -123456;
168

for( i = 1; i <= n2; ++i ){
169

if( line[ i ].bLeft ){
170

left[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
171

}
172

else{
173

right[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
174

}
175

}
176

tree.init( 1, tp );
177

for( i = 1; i <= n; ++i ){
178

tree.modify( left[ i ], right[ i ], i );
179

}
180

}
181

182

private :
183

struct SLine
184

{
185

bool operator<( const SLine & b ){
186

return p < b.p;
187

}
188

int p, id;
189

bool bLeft;
190

};
191

SLine line[ N * 2 ];
192

int left[ N ], right[ N ], n, n2, tp;
193

};
194

195

const int L = 30009, TL = L * 2;
196

CSegTree<TL> tree;
197

CLine<L,TL> line;
198

199

int main(){
200

int td;
201

cin >> td;
202

while( td-- ){
203

cin >> line;
204

line.init_tree( tree );
205

cout << tree.query() << endl;
206

}
207

return 0;
208

}
209

posted on 2012-04-22 22:50 coreBugZJ 閱讀(566) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、DataStructure 、課內作業

只有注冊用戶登錄后才能發表評論。


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 2528 Mayor's posters