This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Author: Tanmoy Datta | |
Solution Idea: | |
- At first take input and store the input in a pair array where first element of i_th pair is the value a_i and second | |
element of i_th pair is i. | |
- Sort the pair array with with ascending order of a_i | |
- Build a merge sort tree using the second element of each pair of sorted pair array. | |
- Now for each query i,j,k at first check how many number in range i to j inclusive are present in left subtree of current | |
node in merge sort tree. Let the value is x. So if x<=k then it's sure that the answer is in the left subtree. So we will | |
go to left subtree of current node with k. Otherwise we will go to right subtree of current node with k-x; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Author: Tanmoy Datta | |
Solution Idea: | |
- Most important observation for this problem is after any update the number must be in range 0 to 300000. | |
- So we can precalculate lcm(1,2,3....X) for every X from 1 to 300000. | |
- Now if you think carefully you will find that lcm of a range in array B comes from the maximum number in the given range | |
in array A and on the other hand gcd come from the minimum. | |
- We can process update and query operation for range update and min max query using a segment tree with lazy propagation. | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
// #include <ext/pb_ds/assoc_container.hpp> | |
// #include <ext/pb_ds/tree_policy.hpp> | |
#define pii pair <int,int> | |
#define pll pair <long long,long long> | |
#define sc scanf | |
#define pf printf | |
#define Pi 2*acos(0.0) | |
#define ms(a,b) memset(a, b, sizeof(a)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
///Using Maxflow Ford Fulkerson | |
#include <bits/stdc++.h> | |
// #include <ext/pb_ds/assoc_container.hpp> | |
// #include <ext/pb_ds/tree_policy.hpp> | |
#define pii pair <int,int> | |
#define pll pair <long long,long long> | |
#define sc scanf |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Author: Tanmoy Datta | |
Solution Idea: | |
--------------- | |
- Make a source. | |
- Make a first group of vertices consisting of n vertices, each of them for one city. | |
- Connect a source with ith vertex in first group with edge that has capacity ai. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#include <ext/pb_ds/assoc_container.hpp> | |
#include <ext/pb_ds/tree_policy.hpp> | |
#define pii pair <int,int> | |
#define pll pair <long long,long long> | |
#define sc scanf | |
#define pf printf | |
#define Pi 2*acos(0.0) | |
#define ms(a,b) memset(a, b, sizeof(a)) |