端端舝

Problem G: Chairs
釬�: aoba
賤掊: 互勻切斤澱
1 / 34

�觳衙猁
- 楓瘍1‵N及N�及眛赽互丐月
- ID1‵N及N�互中化﹜�i反眛赽pi 卞釱曰凶中
- �〝反ID互苤今中�卞1蹈卞�K太﹜蹈互ゴ及�井
日眕狟及紱釬毛俴丹
1. 眛赽pi 互諾炟及�磁反公及炟卞釱月
2. 諾炟匹反卅中�磁反pi 卞1樓呾仄化﹜蹈及郔摽
帣卞�K太眻允(N毛閉尹凶�磁反1午卅月)
- �化及�互釱月引匹仇及紱釬毛靜曰殿允
- 郔皺腔卞公木冗木及眛赽卞釱勻化中月�及ID毛
堤薯允月
- 秶廣: 1 ≒ N ≒ 105, 1 ≒ pi ≒ N
2 / 34

母丟卅賤楊
? �觳恅籵曰卞扑立亙伊奈扑亦件
↙ 瞰尹壬﹜�化及場ヽ弇离互肮元�磁
反N ℅ (N + 1)/2隙及紱釬毛允月仇午卞卅曰
N = 105
卅及匹嶲卞磁歹卅中
3 / 34

禾奶件玄
? �觳毛☆跪眛赽卞�仄化�互�K氏匹中月★
午离五𡥼尹月
4 / 34

賤楊1
? 濛搪睿 + 旦正永弁
5 / 34

賤楊1
? �觳毛离五𡥼尹凶�磁匹手升仇井日升及方丹卅
�唗匹�I燴毛俴丹井毛𢜪戶月斛猁互丐月(�虐允
月凶戶)
? 羥ピ卅弇离毛腢亼允月仇午匹�虐毛眻�午蕉尹
月仇午互匹五月
? 羥ピ卅弇离反棒及方丹卞𢜪戶日木月
1. 跪眛赽卞�仄化場ヽ�毛-1午仄化﹜�互�K氏匹
中月�磁反公及�杅分仃樓呾仄化濛搪睿毛龰
月
2. 公及笢匹郔手�互苤今中�垀毛x午允月午﹜
x + 1互羥ピ卅弇离午卅月(x = N卅日1)
6 / 34

賤楊1
? 羥ピ卅弇离毛腢氏分日公及弇离井日旦正永弁毛
妏中﹜公木冗木及眛赽卞掞互釱月井毛𢜪隅仄化
中仁
? O(N)匹賤仁仇午互匹五月
↗ 馱痲允月午濛搪睿毛妏蚚仄卅仁化手賤仁仇午互
匹五月
7 / 34

賤楊1
8 / 34
N = 8, p = {1, 5, 1, 7, 4, 5, 7, 5}及�磁
1 2 3 4 5 6 7 8
1
3
5 2
6
8
4
7
1 -1 -1 0 2 -1 1 -1

賤楊1
9 / 34
濛搪睿毛龰月
1 2 3 4 5 6 7 8
1
3
5 2
6
8
4
7
1 0 -1 -1 1 0 1 0

賤楊1
10 / 34
眛赽3互郔苤 ↙ 眛赽4井日紱釬毛嶱宎允月
1 2 3 4 5 6 7 8
1
3
5 2
6
8
4
7
1 0 -1 -1 1 0 1 0
start↙

賤楊1
11 / 34
1 2 3 4 5 6 7 8
∣
1
3
5 2
6
8
4
7
Stack

賤楊1
12 / 34
1 2 3 4 5 6 7 8
∣
1
3
2
6
8
4
7
5
Stack

賤楊1
13 / 34
1 2 3
5
4 5 6 7 8
∣
1
3
2
6
8
4
7
Stack

賤楊1
14 / 34
1 2 3
5
4 5 6 7 8
∣
1
3
2
6
8
4
7
Stack

賤楊1
15 / 34
1 2 3
5
4 5 6 7 8
∣
1
3
4
7
2
6
8
Stack

賤楊1
16 / 34
1 2 3
5
4
2
5 6 7 8
∣
1
3
4
7
6
8
Stack

賤楊1
17 / 34
1 2 3
5
4
2
5 6 7 8
∣
1
3
4
7
6
8
Stack

賤楊1
18 / 34
1 2 3
5
4
2
5
6
6 7 8
∣
1
3
4
7
8
Stack

賤楊1
19 / 34
1 2 3
5
4
2
5
6
6 7 8
∣
1
3
4
7
8
Stack

賤楊1
20 / 34
1 2 3
5
4
2
5
6
6 7 8
∣
1
3
4
7
8
Stack

賤楊1
21 / 34
1 2 3
5
4
2
5
6
6
4
7 8
∣
1
3
7
8
Stack

賤楊1
22 / 34
1 2 3
5
4
2
5
6
6
4
7 8
∣
1
3
7
8
Stack

賤楊1
23 / 34
1 2 3
5
4
2
5
6
6
4
7
7
8
∣
1
3
8
Stack

賤楊1
24 / 34
1 2 3
5
4
2
5
6
6
4
7
7
8
∣
1
3
8
Stack

賤楊1
25 / 34
1 2 3
5
4
2
5
6
6
4
7
7
8
∣
1
3
8
Stack

賤楊1
26 / 34
1
1 2 3
5
4
2
5
6
6
4
7
7
8
∣
3
8
Stack

賤楊1
27 / 34
1
1 2 3
5
4
2
5
6
6
4
7
7
8
∣
3
8
Stack

賤楊1
28 / 34
1
1
3
2 3
5
4
2
5
6
6
4
7
7
8
∣
8
Stack

賤楊1
29 / 34
1
1
3
2 3
5
4
2
5
6
6
4
7
7
8
∣
8
Stack

賤楊1
30 / 34
1
1
3
2
8
3
5
4
2
5
6
6
4
7
7
8
∣
Stack

賤楊2
? 扑立亙伊奈扑亦件
? 蹈仍午卞引午戶化�井仄化中仁
? ￤砩及�唗匹蹈毛�井仄化OK
31 / 34

賤楊2
? 跪蹈卞勾中化眕狟及紱釬毛俴丹斛猁互丐月
1. 郔敵曰及諾炟及弇离毛抻允
2. 2勾及蹈毛穴奈斥允月
(珨源及蹈毛手丹珨源及蹈及摽欠卞浲⻌允月)
? 仇木日反瞰尹壬std::set午std::list毛瞎心磁歹六月
午O(logN)匹灍政允月仇午互匹五月
? N�卞勾中化仇及紱釬毛俴丹午O(NlogN)午卅月
32 / 34

磐彆
? Onsite
- First Submission: ca?e 民奈丞 (113 min)
- First Accepted: ca?e 民奈丞 (113 min)
? Online
- First Submission: ei1333 今氏 (49 min)
- First Accepted: ca?e 民奈丞 (113 min)
? Success Rate (Accepted / Submission)
12.00 % (3 / 25)
33 / 34

斥乓永斥賤
aoba C++ 57俴
arrows C++ 49俴
arrows Java 38俴
gacho C++ 25俴
haji C++ 43俴
kawa C++ 17俴
kzyKT C++ 20俴
sate C++ 36俴
uku C++ 66俴
34 / 34

端端舝

賊惚捩唬2017:勞賤掊

Recommended

More Related Content

Viewers also liked (19)

Similar to 賊惚捩唬2017:勞賤掊 (20)

More from Takumi Yamashita (13)

Recently uploaded (7)

賊惚捩唬2017:勞賤掊