Data Structure

Codeforces Round #423C: DNA Evolution

http://codeforces.com/contest/827/problem/Ce int n; ll sum(ll *bit, int i) { ll s = 0; while(i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(ll *bit, int i, ll x) { while(i <= n) { bit[i] += x; i += i & -i; } } struct query { int…

AtCoder Regular Contest 073F: Many Moves

http://arc073.contest.atcoder.jp/tasks/arc073_ddp高速化。dp[i][j]:=(i番目のqueryまで処理して、2点の座標がx[i]とjの時の最小値)とする。 するとdp[i][j]+jとdp[i][j]-jの値についてrange_sumとrange_minが出来れば高速に更新できる。2つsegtreeを持た…

AtCoder Regular Contest 076F: Exhausted?

http://arc076.contest.atcoder.jp/tasks/arc076_d flowのお勉強。Hallの結婚定理より、人の集合Xの誰かが座れる椅子の集合をP(X)と置けば必要な椅子の数はX-P(X)である。椅子の集合は[0,L]or[R,M+1]と表せるのでそこに含まれる最大の人の数を求めればよい。…

AtCoder Regular Contest 072F: Dam

http://arc072.contest.atcoder.jp/submissions/1399394O(N)だからqueueとか使うのかな?と一瞬思ったが、水なんて独立に考えることが出来ないだろ!と思い、O(NlogN)で何とかしようとしたが死亡。水を入れた順番から昇順にdequeで管理することを考える。i番目…

AtCoder Regular Contest 075 E: Meaningful Mean

http://arc075.contest.atcoder.jp/tasks/arc075_c条件を数式に落とし込むと ∑(i=0→r)Ai - rK という値について考えればいいことがわかる。数式を使うと独立性に気付ける問題だった。 あとは適当に座圧してBITで数え上げればよい。 int n; //BIT 1-origin ll…

Educational Codeforces Round 23D: Imbalanced Array

http://codeforces.com/contest/817/problem/D久しぶりにコンテストに参加してみたが、全く頭が動かなかった。これくらいの問題が解けないのは大問題。コンテスト中なぜかいろいろ勘違いして最小値最大値分離出来ねえなあと思っていた。 int N; ll A[MAX_N];…