Segment Tree
Treasures | Aizu Online Judge It's easy to see that we will have to split them into two equal size sets and update the answer for each set to set. Since there are three options for each item, we will have to enumerate all 3 ^ |s| possible …
2019 -- Cornfields ふぁぁ、初めての二次元セグメント木AC。楽しかったです。でも僕はポインタの書き方にしかなれないから、メモリを静態に宣告しなければTLEしてしまいます。でもMAXMEMをちゃんと十分( RE )で多すぎない( MLE ) ように工夫するのは難しい…
School of Killifish | Aizu Online Judge 二次元セグメント木をやるだけ、だと聞きました。でも当たり前にMLEしました。O( n * ( lg ^ 2 ) n ) で n ≤ 1e6。諦めますが、初めての二次元セグメント木で、色々勉強になったので一応MLEしたコードでも載せます…
Problem - 101B - Codeforces dp[ i ][ t[ i ] ] = sum{ dp[ i - 1 ][ s[ i ] .. t[ i ] - 1 ] }, Ɐ i: current bus bus需要先依據終點 t做昇序排序。 注意因為區間範圍可能很大，所以需要離散化。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e9 + 9</bits/stdc++.h>…
Problem - 52C - Codeforces Tag のちょっとした練習になる。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int MAXM = 2e5 + 5; const int MAXABSV = 1e6 + 6; typedef long long ll; const ll INF = 1e16; int n; int a[ MAXN ]; int </bits/stdc++.h>…
House Moving | Aizu Online Judge JOI 11 Day4 Bookshelf ( DP + Segment Tree ) - 0w1 とほぼ同じ。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; #define int long long struct itvt{ int maxv; int lb, rb; itvt *lc, *rc; itvt(int _l = </bits/stdc++.h>…
Bookshelf(本棚) - joi2011-day4 - 情報オリンピック 問題と解説 bookshelf: 本棚 (Bookshelf) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 「この本を動かすかどうか」を直接決めるのはできなさそう。なのでDPを考えてみる。しかし「今の本を動かす」…
Bug Party | Aizu Online Judge 很容易想到，如果固定最小值b，那麼我們必須由小到大拿進所有a，直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和，條件形式複雜，如果不加功夫用持久化線段樹亂搞…
Night Market | Aizu Online Judge ナップサック問題に変換するまでは簡単に見破れるが、問題はどう実装するかだ。愚直に解こうとするとO( n ^ 2 * t )になってしまうので、セグメント木を使いました。実は左からと右からとそれぞれ1回ずつナップサックをす…
C: 列 - AtCoder Beginner Contest 032 | AtCoder Crawling. O( n ). #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXK = 1e9 + 9; typedef long long ll; int n, k; int s[ MAXN ]; void solve(){ if( count( s, s + n, 0 ) ){ pr</bits/stdc++.h>…
C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder Basically we would like to find the element that is covered with the least cost. It is intuitive to use segment tree, but actually we could use imosu algorithm to maintain the differen…
2104 -- K-th Number Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar. First we discretize the integers so that there are at most 1e5 inte…
Mex ( minimum excludant ), has an interesting property in game theory, where an sprague grundy value of a state in a fair game can be deduced from the mex of the sg-values of all the states it could reach in the next step.The definition of…
