0w1

Entries from 2016-03-14 to 1 day

IOI 15 Boxes with Souvenirs ( Greedy )

PEG Judge - IOI '15 - Boxes with Souvenirs 実はそんなに難しくない Greedy。まず、どういう操作があるか考えてみよう。 1、時計回りに動いて逆時計回りに戻る 2、1の真逆 3、一周する 1をする場合は半周を過ぎないのは簡単に見える(そうする必要が…

POJ 2019 Cornfields ( 2D Segment Tree )

2019 -- Cornfields ふぁぁ、初めての二次元セグメント木AC。楽しかったです。でも僕はポインタの書き方にしかなれないから、メモリを静態に宣告しなければTLEしてしまいます。でもMAXMEMをちゃんと十分( RE )で多すぎない( MLE ) ように工夫するのは難しい…

POJ 1631 Bridging signals ( Easy LIS )

POJ

1631 -- Bridging signals tozangezan.hatenablog.com tozangezanさんのブログでセグメント木の問題をたくさんもらいました、ありがとうございます。でもこれだけは。。。LISだけじゃないの?と自分を疑いながらとりあえずか書いてみました。ACしました。ま…

TIOJ 1744 [APIO '09] ATM ( SCC + DP )

1744 - [APIO '09] ATM | TIOJ INFOR Online Judge 題意:給你 n ≤ 5e5 個節點,每個節點都有權重,有些節點是酒吧,接著給你 m ≤ 5e5 個有向邊。給你一個起點,求最後停在一個酒吧( 經過的酒吧可以不要理會 ) 的經過的節點權重總和最大值。同一個節點可以被…

AOJ 1068 School of Killifish ( STILL MLE 2D Segment Tree )

School of Killifish | Aizu Online Judge 二次元セグメント木をやるだけ、だと聞きました。でも当たり前にMLEしました。O( n * ( lg ^ 2 ) n ) で n ≤ 1e6。諦めますが、初めての二次元セグメント木で、色々勉強になったので一応MLEしたコードでも載せます…

CFR 101 B. Buses ( DP + Segment Tree )

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>…

CFR 52 C. Circular RMQ ( Segment Tree )

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>…

AOJ 2431 House Moving ( DP + Segment Tree )

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>…

最近の幾つか小テク

競技プログラミングで陥りやすい言語仕様の罠 - 情報オリンピック 問題と解説 1. これはなんか使えそう。 2. もし intがどこにもあるコードに突然 long longが要求されたら、一番上の行に #define int long long はしたい。しかし、これだと main()が変なも…

JOI 11 Day4 Bookshelf ( DP + Segment Tree )

Bookshelf(本棚) - joi2011-day4 - 情報オリンピック 問題と解説 bookshelf: 本棚 (Bookshelf) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 「この本を動かすかどうか」を直接決めるのはできなさそう。なのでDPを考えてみる。しかし「今の本を動かす」…