Manao is solving a problem with the following statement:
He came up with a solution that produces the correct answers but is too slow. You are given the pseudocode of his solution, where the function getAnswer calculates the answer to the problem:
getAnswer(a[1..n], b[1..len], h)
answer = 0
for i = 1 to n-len+1
answer = answer + f(a[i..i+len-1], b, h, 1)
return answer
f(s[1..len], b[1..len], h, index)
if index = len+1 then
return 1
for i = 1 to len
if s[index] + b[i] >= h
mem = b[i]
b[i] = 0
res = f(s, b, h, index + 1)
b[i] = mem
if res > 0
return 1
return 0
Your task is to help Manao optimize his algorithm.
Input
The first line contains space-separated integers n, len and h (1 ≤ len ≤ n ≤ 150000; 1 ≤ h ≤ 109). The second line contains len space-separated integers b 1, b 2, …, b len (1 ≤ b i ≤ 109). The third line contains n space-separated integers a 1, a 2, …, a n (1 ≤ a i ≤ 109).
Output
Print a single number — the answer to Manao’s problem.
Examples
input
5 2 10
5 3
1 8 5 5 7
output
2
Solution:
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> using namespace std; const int N = 2000010; int mx[N], add[N], a[N], b[N]; void modify(int x, int l, int r, int ll, int rr, int v) { if (l > rr || ll > r) return; if (l >= ll && r <= rr) { add[x] += v; return; } if (add[x] != 0) { add[x + x] += add[x]; add[x + x + 1] += add[x]; add[x] = 0; } int y = (l + r) >> 1; modify(x + x, l, y, ll, rr, v); modify(x + x + 1, y + 1, r, ll, rr, v); mx[x] = mx[x + x + 1] + add[x + x + 1]; if (mx[x + x] + add[x + x] > mx[x]) mx[x] = mx[x + x] + add[x + x]; } int main() { int n, len, h; scanf("%d %d %d", &n, &len, &h); for (int i=1;i<=len;i++) scanf("%d", b+i); sort(b + 1, b + len + 1); reverse(b + 1, b + len + 1); for (int i=1;i<=n;i++) { int foo; scanf("%d", &foo); int ll = 0, rr = len; while (ll < rr) { int mid = (ll + rr + 1) >> 1; if (foo + b[mid] >= h) ll = mid; else rr = mid - 1; } a[i] = ll; } memset(mx, 0, sizeof(mx)); memset(add, 0, sizeof(add)); for (int i=1;i<=len;i++) modify(1, 0, len, i, i, -i); for (int i=1;i<=len-1;i++) modify(1, 0, len, a[i], len, 1); int ans = 0; for (int i=len;i<=n;i++) { modify(1, 0, len, a[i], len, 1); if (mx[1] + add[1] == 0) ans++; modify(1, 0, len, a[i - len + 1], len, -1); } printf("%d\n", ans); return 0; }
Related posts:
New Year and Ascent Sequence
Hongcow Masters the Cyclic Shift
Robot Sequence
Bear and Contribution
Challenges in school №41
Let Them Slide
Bingo!
Princesses and Princes
Reposts
Pavel and barbecue
Remainders Game
Square Table
Road Repairs
Graph Coloring
Cowslip Collections
Gotta Catch Em' All!
Extended Euclidean Algorithm
Vanya and Field
Game with Chips
Metro
Dividing Kingdom
Graph Reconstruction
Kay and Snowflake
Modular Multiplicative Inverse
Sum of Odd Integers
Newton's method for finding roots
Born This Way
Fence Planks
Round Marriage
PolandBall and Gifts
Pearls in a Row
Rational Resistance