Lightoj 1088 - Points in Segments

Problem link:

Analysis:

Just used lower_bound  and upper_bound functions which we all know uses built in binary search function. so for any aray of points like
 a[10] =  {1, 2, 4, 5, 5, 5, 6, 7, 8, 8}
lower_bound(1) = 0              upper_bound(1) = 1        
lower_bound(2) = 1              upper_bound(2) = 2
lower_bound(4) = 2              upper_bound(4) = 3
lower_bound(8) = 8              upper_bound(8) = 10
lower_bound(-500) = 0        upper_bound(10000) = 10
using those you can see lower and upper bound works. than just we find lower bound for left of the segment and upper bound for the right limit of the segment and the difference is our answer.

Here goes the code:

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.     int ts;
5.     scanf("%d", &ts);
6.     for(int p = 1; p <= ts; p++){
7.         printf("Case %d:\n", p);
8.     vector<int>v;
9.     int n, q;
10.     scanf("%d%d", &n, &q);
11.     for(int i = 0; i <n; i++){
12.         int a;
13.         scanf("%d", &a);
14.         v.push_back(a);
15.     }
16.     sort(v.begin(), v.end());
17.     for(int i = 0; i <q; i++){
18.             int l, r;
19.             scanf("%d%d", &l , &r);
20.             printf("%d\n", upper_bound(v.begin(), v.end(),r)-lower_bound(v.begin(), v.end(),l));
21.     }
22.     }
23.     return 0;
24. }

Lightoj 1244 - Tiles

Problem Link:
Explanation:

As we can see here the tiles can not be rotated, so it actually made the problem much simpler.Here goes a little analysis of the problem. We will define 3 functions as follows.

we assume that f(n) is the answer, so

 f(n) = f(n-1) + f(n-2) + g(n-2)+h(n-2),  here f(n-1) because of the vertical tile

f(n-2) because of the horizontal shaped tile and we must use 2 of them reducing to n-2

we assume g(n-2) is similar to f(n-2) accept there is a square in the top corner and this pattern is found when we use type 3 tiles and the symmetric case h(n-2) is same as g(n-2) except this time  that square is in the bottom and this patter is found when we use type 4 tile. So we found the basic function but what is g(n) and h(n) in our known terms?? 

g(n) = f(n-1) + h(n-1); as we can use tile 4 and find structure f(n-1) or we use a horizontal type 2
tile in the bottom and find structure like h(n-1)

h(n)  = f(n-1) + g(n-1) similar case.

 for better visualization go here

so the basic matrix goes like  

[ 1 1 1 1 ]      [  f(n-1) ]     [   f(n)    ]

[ 1 0 0 0 ]  *  [  f(n-2) ] =  [  f(n-1)  ]

[ 0 1 0 1 ]      [ g(n-2) ]     [  g(n-1) ]

[ 0 1 1 0 ]      [ h(n-2) ]     [  h(n-1) ]

Here goes the code: 

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. #define MOD 10007
5. llu cm[4][4];
6. void mul(llu a[4][4],llu b[4][4]){
7.     memset(cm, 0, sizeof(cm));
8.     for(int i = 0; i <4; i++){
9.         for(int j = 0; j <4; j++){
10.             for(int k = 0; k <4; k++){
11.                 cm[i][j]+= ((a[i][k]%MOD)*(b[k][j]%MOD))%MOD;
12.                 cm[j][j]%=MOD;
13.             }
14.         }
15.     }
16.     for(int i = 0; i <4; i++){
17.         for(int j = 0; j <4; j++){
18.             a[i][j] = cm[i][j]%MOD;
19.         }
20.     }
21. }
22. void ans(llu p[4][4], llu n){
23.     llu m[4][4] = {{1,1,1,1},{1,0,0,0},{0,1,0,1}, {0,1,1,0}};
24.     if(n == 1) return;
25.     ans(p, n/2);
26.     mul(p, p);
27.     if(n%2) mul(p, m);
28. }
29. int main(){
30.     int ts;
31.     scanf("%d", &ts);
32.     for(int p = 1; p <= ts; p++){
33.     llu n;
34.     scanf("%llu", &n);
35.     //printf("Case %d:\n", p);
36.     llu f[4][4] = {{1,1,1,1},{1,0,0,0},{0,1,0,1}, {0,1,1,0}};
37.     llu answer1;
38.     if(n == 1) answer1 = 1;
39.     else if(n == 2) answer1 = 2;
40.     else ans(f, n-2),answer1 = (f[0][0]*2)%MOD+f[0][1]%MOD+f[0][2]%MOD+f[0][3]%MOD;
41.     printf("Case %d: %llu\n",p, answer1%MOD);
42.     }
43.     return 0;
44. }

Lightoj 1070 - Algebraic Problem

http://lightoj.com/volume_showproblem.php?problem=1070

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. llu c[2][2];
5. //llu MOD=11221212121121;
6. llu p, q,n;
7. void mul(llu a[2][2],llu b[2][2]){
8.     memset(c, 0, sizeof(c));
9.     for(int i = 0; i <2; i++){
10.         for(int j = 0; j <2; j++){
11.             for(int k = 0; k <2; k++){
12.                 c[i][j]+= ((a[i][k])*(b[k][j]));
13.                 //c[j][j]%=MOD;
14.             }
15.         }
16.     }
17.     for(int i = 0; i <2; i++){
18.         for(int j = 0; j <2; j++){
19.             a[i][j] = c[i][j];
20.         }
21.     }
22. }
23. void ans(llu a[2][2], llu n){
24.     llu m[2][2] = {{p, -q}, {1,0}};
25.     if(n == 1) return;
26.     ans(a, n/2);
27.     mul(a, a);
28.     if(n%2) mul(a, m);
29. }
30. int main(){
31.     int ts;
32.     scanf("%d", &ts);
33.     for(int s = 1; s <= ts; s++){
34.     llu answer;
35.     scanf("%llu%llu%llu",&p, &q, &n);
36.     llu f[2][2] = {{p, -q}, {1,0}};
37.     //llu f1 = p%MOD;
38.     //llu f2 = ((p%MOD)*(p%MOD))%MOD-(2*q)%MOD;
39.     if(n<1) answer = 2;
40.     else if(n == 1) answer = p;
41.     //else if(n == 2) answer  = f2;
42.     else if(n>1) ans(f, n-1), answer = (p*f[0][0]+2*f[0][1]);
43.     printf("Case %d: %llu\n", s,answer);
44.     }
45.     return 0;
46. }

Lightoj 1093 - Ghajini

http://lightoj.com/volume_showproblem.php?problem=1093

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define mx 100001
4. int arr[mx];
5. int tree[mx * 3];
6. int tree1[mx*3];
7. void init(int node, int b, int e)
8. {
9.     if (b == e) {
10.         tree[node] = arr[b];
11.         return;
12.     }
13.     int Left = node * 2;
14.     int Right = node * 2 + 1;
15.     int mid = (b + e) / 2;
16.     init(Left, b, mid);
17.     init(Right, mid + 1, e);
18.     tree[node] = min(tree[Left], tree[Right]);
19. }
20. int query(int node, int b, int e, int i, int j)
21. {
22.     if (i > e || j < b)
23.         return INT_MAX; //বাইরে চলে গিয়েছে
24.     if (b >= i && e <= j)
25.         return tree[node]; //রিলেভেন্ট সেগমেন্ট
26.     int Left = node * 2; //আরো ভাঙতে হবে
27.     int Right = node * 2 + 1;
28.     int mid = (b + e) / 2;
29.     int p1 = query(Left, b, mid, i, j);
30.     int p2 = query(Right, mid + 1, e, i, j);
31.     return min(p1, p2); //বাম এবং ডান পাশের যোগফল
32. }
33.  
34. void init1(int node, int b, int e)
35. {
36.     if (b == e) {
37.         tree1[node] = arr[b];
38.         return;
39.     }
40.     int Left = node * 2;
41.     int Right = node * 2 + 1;
42.     int mid = (b + e) / 2;
43.     init1(Left, b, mid);
44.     init1(Right, mid + 1, e);
45.     tree1[node] = max(tree1[Left], tree1[Right]);
46. }
47. int query1(int node, int b, int e, int i, int j)
48. {
49.     if (i > e || j < b)
50.         return INT_MIN; //বাইরে চলে গিয়েছে
51.     if (b >= i && e <= j)
52.         return tree1[node]; //রিলেভেন্ট সেগমেন্ট
53.     int Left = node * 2; //আরো ভাঙতে হবে
54.     int Right = node * 2 + 1;
55.     int mid = (b + e) / 2;
56.     int p1 = query1(Left, b, mid, i, j);
57.     int p2 = query1(Right, mid + 1, e, i, j);
58.     return max(p1,p2); //বাম এবং ডান পাশের যোগফল
59. }
60. int main()
61. {
62.     int ts;
63.     scanf("%d", &ts);
64.     for(int p = 1; p <=ts; p++){
65.     int n, d;
66.     scanf("%d%d", &n, &d);
67.     for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);  
68.         init(1, 1, n);
69.         init1(1, 1, n);
70.         int l, r;
71.         int ans  = 0;
72.         for(int j = 1; j <=n-d+1; j++){
73.             int s = query(1, 1, n, j, j+d-1);
74.             int r = query1(1, 1, n, j, j+d-1);
75.             //cout<<j<<" = j j+d-1 = "<<j+d-1<<"  s = "<<s<<"  r = "<<r<<endl;
76.             if(s != INT_MAX && r != INT_MIN) ans = max(ans, r-s);
77.         }
78.         printf("Case %d: %d\n", p, ans);
79.     }
80.     return 0;
81. }

Lightoj 1080 - Binary Simulation

http://lightoj.com/volume_showproblem.php?problem=1080

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define mx 100005
4. int a[mx];
5. int n;
6. int update(int indx, int v){
7.     while(indx<=n){
8.         a[indx]+=v;
9.         indx+= (indx&(-indx));
10.     }
11. }
12. int query(int indx){
13.     int sum = 0;
14.     while(indx>0){
15.         sum+= a[indx];
16.         indx-=(indx&(-indx));
17.     }
18.     return sum;
19. }
20. int main()
21. {
22.     int ts;
23.     scanf("%d", &ts);
24.     for(int p = 1; p <=ts; p++){
25.     memset(a, 0, sizeof(a));
26.     printf("Case %d:\n", p);
27.     char s[mx];
28.     scanf("%s", s);
29.     int q;
30.     n = strlen(s);
31.     scanf("%d", &q);
32.         for(int i = 0; i<q ; i++){
33.         char ch;
34.         int l, r, p;
35.         getchar();
36.         scanf("%c", &ch);
37.         if(ch=='I'){
38.             scanf("%d%d", &l, &r);
39.             update(l, 1);
40.             update(r+1, -1);
41.         }
42.         else if(ch == 'Q'){
43.             scanf("%d", &p);
44.             int a = (query(p)%2);
45.             if(a == 0) printf("%c\n", s[p-1]);
46.             else {
47.                 if(s[p-1] == '0') printf("1\n");
48.                 else printf("0\n");
49.             }
50.         }
51.        
52.     }
53.     }
54.     return 0;
55. }