MCMF? solution codeforces
You are given two integer arrays aa and bb (bi≠0bi≠0 and |bi|≤109|bi|≤109). Array aa is sorted in non-decreasing order.
The cost of a subarray a[l:r]a[l:r] is defined as follows:
- If ∑j=lrbj≠0∑j=lrbj≠0, then the cost is not defined.
- Otherwise:
- Construct a bipartite flow graph with r−l+1r−l+1 vertices, labeled from ll to rr, with all vertices having bi<0bi<0 on the left and those with bi>0bi>0 on right. For each i,ji,j such that l≤i,j≤rl≤i,j≤r, bi<0bi<0 and bj>0bj>0, draw an edge from ii to jj with infinite capacity and cost of unit flow as |ai−aj||ai−aj|.
- Add two more vertices: source SS and sink TT.
- For each ii such that l≤i≤rl≤i≤r and bi<0bi<0, add an edge from SS to ii with cost 00 and capacity |bi||bi|.
- For each ii such that l≤i≤rl≤i≤r and bi>0bi>0, add an edge from ii to TT with cost 00 and capacity |bi||bi|.
- The cost of the subarray is then defined as the minimum cost of maximum flow from SS to TT.
You are given qq queries in the form of two integers ll and rr. You have to compute the cost of subarray a[l:r]a[l:r] for each query, modulo 109+7109+7.
MCMF? solution codeforces
If you don’t know what the minimum cost of maximum flow means, read here.
The first line of input contains two integers nn and qq (2≤n≤2⋅105,1≤q≤2⋅105)(2≤n≤2⋅105,1≤q≤2⋅105) — length of arrays aa, bb and the number of queries.
The next line contains nn integers a1,a2…ana1,a2…an (0≤a1≤a2…≤an≤109)0≤a1≤a2…≤an≤109) — the array aa. It is guaranteed that aa is sorted in non-decreasing order.
The next line contains nn integers b1,b2…bnb1,b2…bn (−109≤bi≤109,bi≠0)(−109≤bi≤109,bi≠0) — the array bb.
The ii-th of the next qq lines contains two integers li,rili,ri (1≤li≤ri≤n)(1≤li≤ri≤n). It is guaranteed that ∑j=liribj=0∑j=liribj=0.
For each query lili, riri — print the cost of subarray a[li:ri]a[li:ri] modulo 109+7109+7.
input
Copy
MCMF? solution codeforces
8 4 1 2 4 5 9 10 10 13 6 -1 1 -3 2 1 -1 1 2 3 6 7 3 5 2 6
- Contestants ranked 1st will win a Apple HomePod mini
- Contestants ranked 2nd will win a Logitech G903 LIGHTSPEED Gaming Mouse
- Contestants ranked 3rd ~ 5th will win a LeetCode Backpack
- Contestants ranked 6th ~ 10th will win a LeetCode water bottle
- Contestants ranked 11th ~ 20th will win a LeetCode Big O Notebook
Copy
2 0 9 15
Note
MCMF? solution codeforces
In the first query, the maximum possible flow is 11 i.e one unit from source to 22, then one unit from 22 to 33, then one unit from 33 to sink. The cost of the flow is 0⋅1+|2−4|⋅1+0⋅1=20⋅1+|2−4|⋅1+0⋅1=2.
In the second query, the maximum possible flow is again 11 i.e from source to 77, 77 to 66, and 66 to sink with a cost of 0⋅|10−10|⋅1+0⋅1=00⋅|10−10|⋅1+0⋅1=0.
In the third query, the flow network is shown on the left with capacity written over the edge and the cost written in bracket. The image on the right shows the flow through each edge in an optimal configuration.
