[Solution] MCMF? Codeforces Solution | Codeforces Problem Solution 2022

[Solution] MCMF? Codeforces Solution | Codeforces Problem Solution 2022

F. MCMF?

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two integer arrays 𝑎$a$ and 𝑏$b$ (𝑏𝑖≠0$b_i\ne 0$ and |𝑏𝑖|≤109$|b_i|\le {10}^9$). Array 𝑎$a$ is sorted in non-decreasing order.

The cost of a subarray 𝑎[𝑙:𝑟]$a[l:r]$ is defined as follows:

• If ∑𝑗=𝑙𝑟𝑏𝑗≠0$\sum _{j=l}^r{b}_j\ne 0$, then the cost is not defined.

• Otherwise:

• Construct a bipartite flow graph with 𝑟−𝑙+1$r-l+1$ vertices, labeled from 𝑙$l$ to 𝑟$r$, with all vertices having 𝑏𝑖<0$b_i<0$ on the left and those with 𝑏𝑖>0$b_i>0$ on right. For each 𝑖,𝑗$i,j$ such that 𝑙≤𝑖,𝑗≤𝑟$l\le i,j\le r$, 𝑏𝑖<0$b_i<0$ and 𝑏𝑗>0$b_j>0$, draw an edge from 𝑖$i$ to 𝑗$j$ with infinite capacity and cost of unit flow as |𝑎𝑖−𝑎𝑗|$|a_i-a_j|$.
• Add two more vertices: source 𝑆$S$ and sink 𝑇$T$.
• For each 𝑖$i$ such that 𝑙≤𝑖≤𝑟$l\le i\le r$ and 𝑏𝑖<0$b_i<0$, add an edge from 𝑆$S$ to 𝑖$i$ with cost 0$0$ and capacity |𝑏𝑖|$|b_i|$.
• For each 𝑖$i$ such that 𝑙≤𝑖≤𝑟$l\le i\le r$ and 𝑏𝑖>0$b_i>0$, add an edge from 𝑖$i$ to 𝑇$T$ with cost 0$0$ and capacity |𝑏𝑖|$|b_i|$.

Solution Click Below:-  CLICK HERE

Input

The first line of input contains two integers 𝑛$n$ and 𝑞$q$ (2≤𝑛≤2⋅105,1≤𝑞≤2⋅105)$(2\le n\le 2\cdot {10}^5,1\le q\le 2\cdot {10}^5)$  — length of arrays 𝑎$a$, 𝑏$b$ and the number of queries.

The next line contains 𝑛$n$ integers 𝑎1,𝑎2…𝑎𝑛$a_1,a_2\dots a_n$ (0≤𝑎1≤𝑎2…≤𝑎𝑛≤109)$0\le a_1\le a_2\dots \le a_n\le {10}^9)$  — the array 𝑎$a$. It is guaranteed that 𝑎$a$ is sorted in non-decreasing order.

Palindromic Indices Codeforces Solution

AND Sorting Codeforces Solution 

LIS or Reverse LIS? Codeforces Solution

Circular Spanning Tree Codeforces Solution

Unordered Swaps Codeforces Solution

MCMF? Codeforces Solution

The next line contains 𝑛$n$ integers 𝑏1,𝑏2…𝑏𝑛$b_1,b_2\dots b_n$ (−109≤𝑏𝑖≤109,𝑏𝑖≠0)$(-{10}^9\le b_i\le {10}^9,b_i\ne 0)$  — the array 𝑏$b$.

The 𝑖$i$-th of the next 𝑞$q$ lines contains two integers 𝑙𝑖,𝑟𝑖$l_i,r_i$ (1≤𝑙𝑖≤𝑟𝑖≤𝑛)$(1\le l_i\le r_i\le n)$. It is guaranteed that ∑𝑗=𝑙𝑖𝑟𝑖𝑏𝑗=0$\sum _{j=l_i}^{r_i}{b}_j=0$.

Output

For each query 𝑙𝑖$l_i$, 𝑟𝑖$r_i$  — print the cost of subarray 𝑎[𝑙𝑖:𝑟𝑖]$a[l_i:r_i]$ modulo 109+7${10}^9+7$.