SPOJ

KQUERY - K-query #include <iostream> #include <algorithm> #define pf(i) printf("%ld\n", i) #define sf(i) scanf("%d", &i) #define sl(i) scanf("%ld", &i) using namespace std; int n, q; long int l, r, k; struct node {     int l, r, p;     int v; }; node makenode(int v,int l, int r, int p) {     node temp;     temp.v = v; //value     temp.l = l; //left limit     temp.r = r; //right limit     temp.p = p; //position     return temp; } bool comp(node a, node b) {     if(a.v == b.v)     {         return a.l > b.l;     }     return a.v > b.v; } void update(long int seg[], int l, int r, int index, int pos) {     if(l == r)     {         seg[index]++;     }     else   ...

                           AKVQLD03 - How to Handle the Fans #include <iostream> #include <cstring> #include <cmath> using namespace std; void addNode(long long int seg[], int l, int r, int pos, int index, int val) {     if(l == r)     {         seg[index] += val;     }     else     {         int mid = (l + r) / 2;         if(pos >= l && pos <= mid)         {             addNode(seg, l, mid, pos, 2 * index + 1, val);         }         else         {             addNode(seg, mid + 1, r, pos, 2 * index + 2, val);         }         seg[index] = ...

ANARC05B - The Double HeLiX #include <iostream> #include <cstring> using namespace std; int a[10001]; int b[10001]; int main() {     int n, m;     while(true)     {         cin >> n;         if(n == 0)             break;         for(int i = 0; i < n; i++)         {             cin >> a[i];         }         cin >> m;         for(int i = 0; i < m; i++)         {             cin >> b[i];         }         int i, j;         i = j = 0;         long int sum1, sum2, maxSum;         sum1 = sum2 = max...

KOPC12A - K12 - Building Construction #include <iostream> #include <cmath> #define REP(i, n) for(int i = 0; i < n; i++) using namespace std; const int N = 10005; int height[N]; int cost[N]; int n; //finds the total cost for height h long long int findCost(int h) {     long long c = 0; //cost     REP(i, n)     {         c += abs(h - height[i]) * cost[i];     }     return c; } int ternary_search(int l, int h) {     while(l <= h)     {         if(l == h)             break;         int mid1 = l + (h - l) / 3;         int mid2 = h - (h - l) / 3;         if(findCost(mid1) > findCost(mid2))             l = mid1 + 1;         else ...

ANARC09A - Seinfeld #include <iostream> #include <stack> using namespace std; stack<char> st; int main() {     string s;     int c, k;     k = 1;     while(true)     {         cin >> s;         c = 0;         if(s[0] == '-')             break;         for(int i = 0; i < s.size(); i++)         {             st.push(s[i]);             //stack contains } and { then we can safely remove them from stack             if(st.top() == '}' && st.size() != 1)             {                 char a = st.top();               ...

ADFRUITS-Advanced Fruits #include <iostream> using namespace std; int dp[101][101]; char str[202]; int main() {     string a, b;     int l1, l2, i, j;     while(cin >> a >> b)     {         l1 = a.size();         l2 = b.size();         //max length of common substring         for(i = 0; i <= l1; i++)         {             for(j = 0; j <= l2; j++)             {                 if(i == 0 || j == 0)                     dp[i][j] = 0;                 else                 {                   ...

GIRLSNBS - Girls and Boys #include <iostream> using namespace std; int main() {     int g, b, result;     while(true)     {         cin >> g >> b;         if(g == -1 && b == -1)             break;         if(g < b)         {             int temp = g;             g = b;             b = temp;         }         if(g == 0 && b == 0)         {             cout << "0\n";             continue;         }         if(b == 0)         {             cout <...

LASTDIG2 - The last digit re-visited #include <iostream> using namespace std; string s; int main() {     int t, i;     long long int a, b, d;     cin >> t;         while(t--)     {              cin >> s;                  cin >> b;         i = s.size() - 1;         a = (s[i] - '0');         d = 1;         while(b)         {             if(b & 1)             {                 d = (d * a) % 10;             }             a = (a * a) % 10;             b = b...

MAIN72 - Subset sum #include <iostream> #include <cstring> using namespace std; bool dp[100001][1001]; int arr[1001]; int main() {     int t, n;     long long int sum;     cin >> t;     while(t--)     {         cin >> n;         memset(dp, false, sizeof(dp));         sum = 0;         for(int i = 0; i < n; i++)         {             cin >> arr[i];             sum += arr[i];         }         for(int i = 0; i < n; i++)             dp[0][i] = true; // 0 sum         for(int i = 1; i < n; i++)             dp[i][0] = false; // sum is i but 0 element         for(long int i =...

LASTDIG - The last digit #include <iostream> #define ll long long int using namespace std; ll expo(ll a, ll b, int n) {     ll d = 1;     while(b)     {         if((b & 1))         {             d = (d * a) % n;         }         b = b >> 1;         a = (a * a) % n;     }     return d; } int main() {     int t;     ll a, b;     cin >> t;     while(t--)     {         cin >> a >> b;         cout << expo(a, b, 10) << endl;     }     return 0; }

FACT0 - Integer Factorization (15 digits) #include <iostream> using namespace std; int main() {     long long int n;     int c;     while(true)     {         cin >> n;         if(n == 0)             break;         c = 0;         while(!(n & 1))         {             n = n / 2;             c++;         }         if(c)             cout << "2^" << c << " ";         for(long long i = 3; i * i <= n; i += 2)         {             c = 0;             while(n % i == 0)             {     ...

CRDS - Cards #include <iostream> using namespace std; long int m = 1000007; int main() {     int t;     long long int n;     long long int result;     cin >> t;     while(t--)     {         cin >> n;         result = 0;         result += 3 * (n * (n + 1) / 2) - n;         result = result % m;         cout << result << endl;     }     return 0; }

BYTESM2 - Philosophers Stone #include <iostream> #include <algorithm> using namespace std; int main() {     int t, h, w, m, temp;     cin >> t;     while(t--)     {         cin >> h >> w;         m = 0;         temp = 0;         int arr[h][w];         for(int i = 0; i < h; i++)         {             for(int j = 0; j < w; j++)             {                 cin >> arr[i][j];             }         }         for(int i = 1; i < h; i++)         {             for(int j = 0; j < w; j++)             {  ...

ETF - Euler Totient Function #include <iostream> #include <vector> using namespace std; const int N = 1000001; vector<int> p; void sieve() {     bool prime[N] = {false};     for(int i = 3; i * i <= N; i += 2)     {         if(!prime[i])         {             for(int j = i * i; j <= N; j += i)             {                 prime[j] = true;             }         }     }     p.push_back(2);     for(int i = 3; i <= N; i += 2)     {         if(!prime[i])             p.push_back(i);     } } int main() {     int t, n;     float result;     cin >> t;     sieve(); ...