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