LightOJ - 1093 - Ghajini

1. #include <bits/stdc++.h>
2. #define sc(n) scanf("%d", &n)
3. #define L 100003
4. using namespace std;
5.  
6. struct data{
7.     int mxx, mnn;
8. }Tree[L*3];
9.  
10. int Mem[L], N, D, ans, maxx;
11.  
12. void Build(int s, int e, int node){
13.     if(s >= e){
14.         if(s == e)Tree[node].mxx = Tree[node].mnn = Mem[s];
15.         return;
16.     }
17.     int mid = (s+e)/2, leafL = node*2, leafR = leafL+1;
18.     Build(s, mid, leafL);
19.     Build(mid+1, e, leafR);
20.     Tree[node].mxx = max(Tree[leafL].mxx, Tree[leafR].mxx);
21.     Tree[node].mnn = min(Tree[leafL].mnn, Tree[leafR].mnn);
22. }
23. data Query(int s, int e, int node, int i, int j){
24.     if(s >= i && e <= j){
25.         return Tree[node];
26.     }
27.     if(s > j || e < i){
28.         data Pre;
29.         Pre.mxx = 0;
30.         Pre.mnn = INT_MAX;
31.         return Pre;
32.     }
33.     int mid = (s+e)/2, leafL = node*2, leafR = leafL+1;
34.     data x = Query(s, mid, leafL, i, j);
35.     data y = Query(mid+1, e, leafR, i, j);
36.     int mx = 0, mn = INT_MAX;
37.     mx = max(mx, max(x.mxx, y.mxx));
38.     mn = min(mn, min(x.mnn, y.mnn));
39.     data ret;
40.     ret.mxx = mx;
41.     ret.mnn = mn;
42.     return ret;
43. }
44.  
45. int searchAns(int s, int e){
46.     if(e > N)return 0;
47.     data Quu = Query(1, N, 1, s, e);
48.     int sum = Quu.mxx-Quu.mnn;
49.     maxx = max(maxx, sum);
50.     searchAns(s+1, e+1);
51.     return maxx;
52. }
53.  
54. int main(){
55.     int t, cs = 0;
56.     sc(t);
57.     while(t--){
58.         maxx = 0;
59.         sc(N);sc(D);
60.         for(int i = 1; i <= N; i++)sc(Mem[i]);
61.         Build(1, N, 1);
62.         int ans = searchAns(1, D);
63.         printf("Case %d: %d\n", ++cs, ans);
64.     }
65.     return 0;
66. }