Skip to content

Instantly share code, notes, and snippets.

View shobhit6993's full-sized avatar

Shobhit Chaurasia shobhit6993

15 followers · 0 following
View GitHub Profile
@shobhit6993
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
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
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
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
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
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
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
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
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=='-')