shobhit6993’s gists

shobhit6993 / dijkstra.hs

Created August 11, 2014 19:03

Haskell implementation of the Dijkstra's Single-Source Shortest Path Algorithm.

	--sample input
	--dijkstra source dest [(n1,n2,e1),(n3,n4,e2)...] [(source,0)]
	--dijkstra 1 4 [(1,2,5),(1,3,10),(2,4,100),(3,4,20)] [(1,0)]
	--dijkstra 1 5 [(1,2,2), (2,3,1), (3,5,3), (4,5,4), (1,4,5), (1,3,8)] [(1,0)]

	--ouput
	-- a list of tuples with each tuple (n1,d1) representing the min. dist d1 of node n1 from source

	inf = 100000

shobhit6993 / segTree_lazy_sum2.cpp

Created October 25, 2013 03:59

Another implementation of segment tree with lazy propagation with sum of intervals operation



	#include <cstdio>
	#include <iostream>
	#include <string.h>

	using namespace std;

	#define l(n) 2*n
	#define r(n) 2*n+1

shobhit6993 / segmentTree_lazy_sum.cpp

Created October 25, 2013 03:45

Segment tree with lazy propagation for sum of intervals operation.

	#include <iostream>
	#include <string>
	#include <limits>
	#include <cstdio>
	#include <cstdlib>
	#include <cmath>
	#include <vector>
	#include <algorithm>
	#include <utility>
	#include <queue>

shobhit6993 / segmentTree_lazy_min.cpp

Last active June 6, 2023 21:24 — forked from Se7soz/lazy_segment_tree.cpp

C++ implementation of segment tree with lazy propagation.

	/**
	* In this code we have a very large array called arr, and very large set of operations
	* Operation #1: Increment the elements within range [i, j] with value val
	* Operation #2: Get max element within range [i, j]
	* Build tree: build_tree(1, 0, N-1)
	* Update tree: update_tree(1, 0, N-1, i, j, value)
	* Query tree: query_tree(1, 0, N-1, i, j)
	* Actual space required by the tree = 2*2^ceil(log_2(n)) - 1
	*/

shobhit6993 / segment_tree.cpp

Last active May 1, 2023 10:12 — forked from Se7soz/segment_tree.cpp

Implementation of segment tree without lazy propagation.

	/**
	* In this code we have a very large array called arr, and very large set of operations
	* Operation #1: Increment the elements within range [i, j] with value val
	* Operation #2: Get max element within range [i, j]
	* Build tree: build_tree(1, 0, N-1)
	* Update tree: update_tree(1, 0, N-1, i, j, value)
	* Query tree: query_tree(1, 0, N-1, i, j)
	* Actual space required by the tree = 2*2^ceil(log_2(n)) - 1
	*/

shobhit6993 / PowMod_nonrecursive.cpp

Created October 17, 2013 13:48

This is a non-recursive implementation of exponentiation in O(log(n)) with MOD. Takes up more space as compared to the recursive implementation.

	//non recursive version
	int64_t powMod(int64_t a,int64_t power)
	{
	if (a==1)
	{
	return 1;
	}

	int64_t count=0, answer=1;
	std::vector<int64_t> powerDP;

shobhit6993 / PowMod_recursive.cpp

Created October 17, 2013 13:45

Simple recursive function for exponentiation in O(log(n)) time with Mod.

	//recursive version
	int64_t powMod(int64_t base,int64_t expo)
	{
	if(expo==0)
	{
	return 1;
	}
	else if(expo%2==0)
	{
	int64_t ans=powMod(base,expo/2);

shobhit6993 / bigInt_C++.cpp

Created October 17, 2013 13:25

This code is the implementation of an equivalent of Java's BigInt class in C++.

	#include <vector>
	#include <cstdlib>
	#include <iostream>
	#include <iomanip>
	#include <string>
	using namespace std;
	typedef long long LL;
	// base and base_digits must be consistent
	const int base = 1000000000;
	const int base_digits = 9;

shobhit6993 / fastRead.cpp

Last active September 13, 2016 02:30

This easy-to-understand and easy-to-code snippet comes handy while taking fast integer (negative as well as positive) inputs in coding competitions and online judges like SPOJ, Codechef etc. The getchar_unlocked() function might not work on some judges like CodeForces, where getchar() can be used instead. Slight modification can be done to make …

	inline void fastRead(int n,std::vector<int> &input)
	{
	for (int i = 0; i < n; ++i)
	{
	int sign=1;
	register char c=0;
	while(c<'0' \|\| c>'9')
	{
	c=getchar_unlocked();
	if (c=='-')

Shobhit Chaurasia shobhit6993