Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int mx = 1e5+10;
- int arr[mx];
- int tree[4*mx];
- void init1(int node,int b,int e)
- {
- if(b==e)
- {
- tree[node] = arr[b];
- return;
- }
- int left = node * 2;
- int right = node *2+1;
- int mid = (b+e)/2;
- init1(left,b,mid);
- init1(right,mid+1,e);
- tree[node]=max(tree[left],tree[right]);
- }
- int query1(int node,int b,int e,int i,int j)
- {
- if(i>e || j<b)
- return 0;
- if(b>=i && e<=j)
- return tree[node];
- int left = node * 2;
- int right = node * 2 + 1;
- int mid = (b+e)/2;
- int p = query1(left,b,mid,i,j);
- int q = query1(right,mid+1,e,i,j);
- return max(p,q);
- }
- void init(int node,int b,int e)
- {
- if(b==e)
- {
- tree[node] = arr[b];
- return;
- }
- int left = node * 2;
- int right = node *2+1;
- int mid = (b+e)/2;
- init(left,b,mid);
- init(right,mid+1,e);
- tree[node]=min(tree[left],tree[right]);
- }
- int query2(int node,int b,int e,int i,int j)
- {
- if(i>e || j<b)
- return 0;
- if(b>=i && e<=j)
- return tree[node];
- int left = node * 2;
- int right = node * 2 + 1;
- int mid = (b+e)/2;
- int p = query2(left,b,mid,i,j);
- int q = query2(right,mid+1,e,i,j);
- return min(p,q);
- }
- int main()
- {
- int t,cnt=1;
- scanf("%d",&t);
- while(t--)
- {
- int n,d;
- scanf("%d%d",&n,&d);
- for(int i=0; i<n; i++)
- scanf("%d",&arr[i]);
- init1(1,0,n-1);
- init(1,0,n-1);
- int ans =-1;
- for(int i=0; i<=n-d; i++)
- {
- ans = max(ans,abs(query1(1,0,n-1,i,i+d-1)-query2(1,0,n-1,i,i+d-1)));
- }
- printf("Case %d: ",cnt++);
- printf("%d",ans);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement