WAV2 problem time limit exceeded?

help
,
1

My issue

My code

#include <iostream>
using namespace std;

int main() {
	int n,q,sum,pol,prod;
	cin>>n>>q;
	int t[n];
	int x[q];
	for(int i=0;i<n;i++){
	    cin>>t[i];
	}
	for(int i=0;i<q;i++){
	    cin>>x[i];
	}
	int j=0;
	while(q--){
	prod=1;
     for(int i=0;i<n;i++){
            pol=(x[j]-t[i]);
            prod=prod*pol;
     }
     if(prod>0){
         cout<<"POSITIVE"<<endl;
     }
     else if(prod<0){
         cout<<"NEGATIVE"<<endl;
     }
     else{
         cout<<0<<endl;
     }
     j++;
}
	return 0;
}

Problem Link: WAV2 Problem - CodeChef

2

@amnkhxn
U r getting tle bcoz inside q loop u can’t do O(n) complexity cozz it will make it as O(N^2).
One hint
Try binary search inside q loop.