1082 - Array Queries

Problem Link

Solution:

	#include<bits/stdc++.h>
	using namespace std;
	#define MAX 1234567
	int arr[MAX];
	int tree[4*MAX];
	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 query(int node, int b, int e, int i, int j)
	{
	if (i > e || j < b)
	return INT_MAX;
	if (b >= i && e <= j)
	return tree[node];
	int Left = node * 2;
	int Right = node * 2 + 1;
	int mid = (b + e) / 2;
	int p1 = query(Left, b, mid, i, j);
	int p2 = query(Right, mid + 1, e, i, j);
	if(p1>p2)
	return p2;
	return p1;
	}
	int main()
	{
	int T;
	scanf("%d",&T);
	for(int t = 1; t <= T; t++)
	{
	int N, q;
	scanf("%d %d",&N,&q);
	for(int i = 1; i <= N; i++)
	{
	scanf("%d",&arr[i]);
	}
	init(1,1,N);
	/*for(int i = 1; i <= 9; i++)
	cout<<tree[i]<<endl;*/
	printf("Case %d:\n",t);
	for(int i = 1; i <= q; i++)
	{
	int l, r;
	scanf("%d %d",&l,&r);
	printf("%d\n",query(1,1,N,l,r));
	}
	}
	return 0;
	}

view raw 1082.cpp hosted with ❤ by GitHub