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:
Rational Resistance
Number of Ways
Sparse Table
Drazil Likes Heap
Design Tutorial: Learn from Math
Work Group
New Year and the Christmas Ornament
Rotate Columns (easy version)
Security
Captain Marmot
Depth First Search
Worms
Permutation Game
Property
Paint the Numbers
Happy Cactus
Tree Diameter
Finding articulation points in a graph in $O(N+M)$
Red Blue Tree
Eugene and an array
Gambling Nim
Playing on Graph
Bribes
Om Nom and Necklace
Bad Ugly Numbers
Carrot Cakes
Double Permutation Inc
Sereja and Sets
Rusty String
Keyboard
Alyona and a Narrow Fridge
Speckled Band