Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

POI 18 Stage 3 Meteors ( Parallel Binary Search, Fenwick Tree )

http://main.edu.pl/en/archive/oi/18/met題意: 有 M 個環狀的地,每個地屬於一個人。有 K 次隕石事件,每次會在某一連續區間 [ L[ i ], R[ i ] ] 每個地分別降下有 W[ i ] 單位的隕石。有 N 個人,每個人有最少需要收集的隕石量 P[ i ]。要求分別輸出每個…

POI 2 Stage 3 Coding of Permutations ( Fenwick Tree, Binary Search )

http://main.edu.pl/en/archive/oi/2/kod題意: 給一個序列 B,問是否有一個 [ 1, | B | ] 的排列 A,使得 B[ i ] 等於 A[ 0, i ) 中比 A[ i ] 大的數字的數量。輸出方案。資料規模: In the first line of the standard input there is a positive integer …

CFR 785 E. Anton and Permutation ( RBST on BIT )

Problem - E - Codeforces題意: 一開始你有一個序列 P = { 1, 2, 3, .. N }。處理 Q 筆永久詢問,給 L, R,將 P[ L ] 和 P[ R ] 交換後,輸出當前 P 的逆序述對數。資料規模: The first line of the input contains two integers n and q (1 ≤ n ≤ 200 000…

CFR 314 C. Sereja and Subsequences ( DP, BIT )

Problem - 314C - Codeforces題意: 給一個 N 個數組成的數列 A。現在有人把 A 的所有相異的非遞減子序列都生出來了。輸出,對這些子序列分別求,不比該子序列的字典序大的所有子序列的方案數,的總和,對 1e9 + 7 取模。資料規模: The first line contains…

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 的人從前…

CFR 179 1A. Greg and Array ( BIT )

Problem - A - Codeforces 二回べつべつに区間操作するのは自明。まずどの操作が何回使われるかを統計して終えてから操作毎に区間addをすればいい。 Range add と Single query しかないので BITの方がかなり楽。 追記:いや、普通にarrayの上でいもすすれば…

JOI 10 本選 Planetary Exploration ( 二次元BIT )

Planetary Exploration | Aizu Online Judge なにも考えずに一番先に頭から出たのが二次元BIT。普通にprefix sumでもいけるけど、BITは応用が効くからこれで。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1000 + 3; const int MAXM = 1000 + 3; const</bits/stdc++.h>…

ABC 17 C - ハイスコア ( Imosu or Segment Tree )

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…

CFR 635 D. Factory Repairs ( BIT )

Problem - D - Codeforces Notice that if the maintenance is made on day p, the maximum sum it could take is prefix sum of min( b, val[ i ] ) + suffix sum of min( a, val[ j ] ) Ɐ i and since the queries are forced to be solved online, we wil…