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     {         int mid = (l + r) / 2;         if(pos <= mid)         {             update(seg, l, mid, 2 * index + 1, pos);         }         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] = seg[2 * index + 1] + seg[2 * index + 2];     } } int findSum(long long int seg[], int l, int r, int qs, int qe, int index) {     if(qe < l || qs > r)         return 0;     if(qs <= l && qe >= r)         return seg[index];     int mid = (l + r) / 2;     int p1 = findSum(seg, l, mid, qs, qe, 2 * index + 1);

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 = maxSum = 0;         while(i < n && j < m)         {             if(a[i] < b[j])             {                 sum1 += a[i];                 i++;             }             else if(b[j] < a[i])             {                 sum2 += b[j];                 j++;             }             else             {                 maxSum += ma

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             h = mid2 - 1;     }     return l; } int main() {     int t, maxHeight;     cin >> t;     while(t--)     {         cin >> n;         maxHeight = 0;         REP(i, n)         {          

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();                 st.pop();                 char b = st.top(); // if b != { do not remove and push back a also                 if(a != b)                     st.pop();                 else                     st.push(a);             }         }         while(!st.empty())         {             char a = st.top();             st.pop();             ch

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                 {                     if(a[i - 1] == b[j - 1])                     {                         dp[i][j] = dp[i - 1][j - 1] + 1;                     }                     else                     {                         dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);                     }                 }             }         }         int index = dp[l1][l2];         char lcs[index + 1];         lcs[inde

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 << g << "\n";             continue;         }         if(g == b)         {             cout << "1\n";             continue;         }         b = b + 1;         result = g / (b);         if(g % b != 0)             result++;         cout << result << "\n";     }     return 0; }

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 >> 1;         }         cout << d << endl;     }     return 0; }

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 = 1; i <= sum; i++)         {             for(int j = 1; j <= n; j ++)             {                 dp[i][j] = dp[i][j - 1];                 if(i >= arr[j - 1])                     dp[i][j] = dp[i][j] || dp[i - arr[j - 1]][j - 1];             }         }         long int result = 0;         for(int i = 1; i <= sum; 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)             {                 n = n / i;                 c++;             }             if(c)                 cout << i << "^" << c << " ";         }         if(n != 1)             cout << n << "^1";         cout << endl;     }     return 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++)             {                 temp = arr[i - 1][j];                 if(j > 0)                 {                     temp = max(temp, arr[i - 1][j - 1]);                 }                 if(j < w - 1)                 {                     temp = max(temp, arr[i - 1][j + 1]);                 }                 arr[i][j] += temp;             }         }         for(int i = 0; i < w; i++)         {      

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();     while(t--)     {         cin >> n;         result = n;         for(int i = 0; i < p.size() && p[i] * p[i] <= n; i++)         {             if(n % p[i] == 0)             {                 result *= (1.0 - 1.0 / (float)p[i]);                 while(n % p[i] == 0)                     n = n / p[i];             }