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. }

Lightoj 1164 - Horrible Queries

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

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define mx 100001
4. int arr[mx];
5. #define ll long long unsigned
6. struct info {
7.     ll prop, sum;
8. } tree[mx * 3];
9.  
10. void init(int node, int b, int e)
11. {
12.     if (b == e) {
13.         tree[node].sum = arr[b];
14.         tree[node].prop = 0;
15.         return;
16.     }
17.     int Left = node * 2;
18.     int Right = node * 2 + 1;
19.     int mid = (b + e) / 2;
20.     init(Left, b, mid);
21.     init(Right, mid + 1, e);
22.     tree[node].sum = (tree[Left].sum+ tree[Right].sum);
23.     tree[node].prop = 0;
24. }
25. ll query(int node, int b, int e, int i, int j, ll carry = 0)
26. {
27.     if (i > e || j < b)
28.         return 0;
29.  
30.     if (b >= i and e <= j)
31.         return tree[node].sum + carry * (e - b + 1); //সাম এর সাথে যোগ হবে সেই রেঞ্জের সাথে অতিরিক্ত যত যোগ করতে বলেছে সেটা
32.  
33.     int Left = node << 1;
34.     int Right = (node << 1) + 1;
35.     int mid = (b + e) >> 1;
36.  
37.     ll p1 = query(Left, b, mid, i, j, carry + tree[node].prop); //প্রপাগেট ভ্যালু বয়ে নিয়ে যাচ্ছে carry ভ্যারিয়েবল
38.     ll p2 = query(Right, mid + 1, e, i, j, carry + tree[node].prop);
39.  
40.     return p1 + p2;
41. }
42. void update(int node, int b, int e, int i, int j, ll x)
43. {
44.     if (i > e || j < b)
45.         return;
46.     if (b >= i && e <= j) //নোডের রেঞ্জ আপডেটের রেঞ্জের ভিতরে
47.     {
48.         tree[node].sum += ((e - b + 1) * x); //নিচে নোড আছে e-b+1 টি, তাই e-b+1 বার x যোগ হবে এই রেঞ্জে
49.         tree[node].prop += x; //নিচের নোডগুলোর সাথে x যোগ হবে
50.         return;
51.     }
52.     int Left = node * 2;
53.     int Right = (node * 2) + 1;
54.     int mid = (b + e) / 2;
55.     update(Left, b, mid, i, j, x);
56.     update(Right, mid + 1, e, i, j, x);
57.     tree[node].sum = tree[Left].sum + tree[Right].sum + (e - b + 1) * tree[node].prop;
58.     //উপরে উঠার সময় পথের নোডগুলো আপডেট হবে
59.     //বাম আর ডান পাশের সাম ছাড়াও যোগ হবে নিচে অতিরিক্ত যোগ হওয়া মান
60. }
61.  
62. int main()
63. {
64.     int ts;
65.     scanf("%d", &ts);
66.     for(int p = 1; p <=ts; p++){
67.     memset(arr, 0, sizeof(arr));
68.     memset(tree, 0, sizeof(tree));
69.     printf("Case %d:\n", p);
70.     int n, q;
71.     scanf("%d%d", &n, &q);
72.     //for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);
73.         //init(1, 1, n);
74.         for(int i = 0; i<q ; i++){
75.             int num;
76.             scanf("%d", &num);
77.             if(num == 0){
78.                 int x, y, v;
79.                 scanf("%d%d%d", &x, &y, &v);
80.                 update(1, 1, n, x+1, y+1, v);
81.             }
82.             else if(num == 1){
83.                 int x, y;
84.                 scanf("%d%d", &x, &y);
85.                 printf("%lld\n", query(1, 1, n, x+1, y+1, 0));
86.             }
87.     }
88.     }
89.     return 0;
90. }
91.