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 <iostream> | |
#include <vector> | |
#include <cstdio> | |
#include <algorithm> | |
using namespace std; | |
int a,num[120000],n,ans[120000],sz; | |
int main(){ | |
while (scanf("%d",&n) == 1){ |
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<iostream> | |
#include<algorithm> | |
using namespace std; | |
#include<string.h> | |
#include<math.h> | |
#define N 20 | |
#define MAX (1+(1<<6)) // Why? :D | |
#define inf 0x7fffffff |
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
void update(int x , int y , int val){ | |
while (x <= max_x){ | |
updatey(x , y , val); | |
// this function should update array tree[x] | |
x += (x & -x); | |
} | |
} | |
void updatey(int x , int y , int val){ | |
while (y <= max_y){ |
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
Isolating the last digit | |
NOTE: Instead of "the last non-zero digit," it will write only "the last digit." | |
There are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit. | |
Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have | |
-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0...0)¯ + 1 = a¯0(1...1) + 1 = a¯1(0...0) = a¯1b. | |
Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and -num: | |
a1b |
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
#define getcx getchar_unlocked | |
inline void inp( int &n )//fast input function | |
{ | |
n=0; | |
int ch=getcx();int sign=1; | |
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} | |
while( ch >= '0' && ch <= '9' ) | |
n = (n<<3)+(n<<1) + ch-'0', ch=getcx(); | |
n=n*sign; |
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<iostream> | |
using namespace std; | |
#include<vector> | |
/* This function calculates (a^b)%MOD */ | |
long long pow(int a, int b, int MOD) | |
{ | |
long long x=1,y=a; | |
while(b > 0) | |
{ |
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
RANGE QUERY | |
Given a (big) array r[0..n-1], and a lot of queries of certain type. We may want to pre-process the data so that each | |
query can be performed fast. In this section, we use T (f, g) to denote the running time for an algorithm is O(f(n)) | |
for pre-processing, and O(g(n)) for each query. | |
If the queries are of type getsum(a, b), which asks the sum of all the elements between a and b, inclusive, | |
we have a T (n, 1) algorithm: Compute s[i] to be the sum from r[0] to r[i-1], inclusive, then getsum(a,b) simply | |
returns s[b+1]-s[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
The Naive pattern searching algorithm doesn’t work well in cases where we see many matching characters followed by | |
a mismatching character. Following are some examples. | |
txt[] = "AAAAAAAAAAAAAAAAAB" | |
txt[] = "ABABABCABABABCABABABC" | |
lps[i] = the longest proper prefix of pat[0..i] Searching Algorithm:Preprocessing Algorithm: | |
if (pattern[0] == '\0') /* Construct the lookup table */ /* Perform the search */ free(T); | |
pat[] = "AAAAB" |
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
Iterative version | |
int jos(int K,int N) | |
{ | |
int r =0; | |
for(int i=1;i<=N;i++) | |
{ |