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

Lightoj 1112 - Curious Robin Hood

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

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