0w1

Deque

ARC 072 F - Dam ( Greedy, Monotonous, Deque )

F: Dam - AtCoder Regular Contest 072 | AtCoder題意: 有一個水壩,容量是 L。有 N 天,第 i 天早上會有溫度 T[ i ] 容量 V[ i ] 的水流進水壩,晚上你可以讓水壩流出任意適當多容量的水。分別對於 [ 1, N ] 的所有 i,問使得第 i 天恰有容量 L 的水在水壩…

Yuki 489 株に挑戦 ( Sliding Window )

No.489 株に挑戦 - yukicoder題意: 買賣股票,買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i 制約: 2 ≤ N ≤ 1e5 1 ≤ D 1 ≤ K ≤ 1e6 1 ≤ xi ≤ 1e6解法: 努力寫了一次線段樹,但 python 也很給力的 TLE 了。 經典的滑動視窗: window[ i ]: i …

IOICJ 109 Big Tower ( DP, Deque )

Problem Description: There is a tower with N floors, each floor having M rooms in order. One receives score S[ i ][ j ] when being at the j'th room of the i'th floor. You start at the X'th room at the first floor. Your objective is to trav…

CFR 487 B. Strip ( DP, Monotonic Deque )

Problem - B - Codeforces題意: 給你 n 個數組成的數列 a,和總和上限 s,長度下限 l。求將數列 a 分割成最少數量的連續片段,滿足每個片段總和不超過 s,長度不小於 l。求最少可能片段數量。資料規模: 1 ≤ n ≤ 1e5, 0 ≤ s ≤ 1e9, 1 ≤ l ≤ 1e5,- 1e9 ≤ ai …

Bangladesh OI 2016 National Round pA. Guess the Queue ( BIT + Deque )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意: 實現一個雙向佇列,可以回答以下三種詢問: 1. ‘1 x y’ ID 為 y 的人從前…

Yuki 6 使いものにならないハッシュ ( Deque )

No.6 使いものにならないハッシュ - yukicoder題意: 給 L, R,代表所求區間 [ L, R ] 中,如程式碼中的 get_hash() 函數,最長區間 [ l, r ] 滿足 get_hash( i | l ≤ i ≤ r ) 皆相異,其最大可能的 l。資料規模: L, R ≤ 2e5解法: 用 deque,從後面掃回來…

CFR 644 B. Processing Queries ( Deque Implementation )

Problem - B - Codeforces 適当に queueでやってWAもらいました。 Dequeで終了時間を抑える方が合ってるそうです。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int MAXB = MAXN; const int MAXT = 1e9 + 9; const int MAXD = 1e9 + 9;</bits/stdc++.h>…

TIOJ 1063 Area ( Deque Monotonicity )

1063 - 最大矩形(Area) | TIOJ INFOR Online Judge 跟這題很像的,不過這次是要求矩形面積。 UVA 12265 Selling Land ( Stack Monotonicity ) - 0w1 很容易注意到,如果先發生的( 左邊開始的 )矩形比後發生的矩形高,那只要先發生的矩形好好的,後面發生的矩…

CFR 631 E. Product Sum ( Convex hull trick DP )

Problem - E - Codeforces pekempeyさんの記事と公式の editorialよりいい解釈はないと思うのでとりあえず。 pekempey.hatenablog.com Editorial Codeforces Round #344 (Div. 2) - Codeforces For this problem, we will consider convex hull trick. There…

Introduction to deque optimizations

A deque ( double ended queue ) is a data structure that supports push/ pop from both ends with constant time complexity. It can be used to optimize algorithms that deal with monotonous properties. The first time I saw this data structure, …