fork(1) download
copy 
  1. //package pawan;
  2. import java.util.*;
  3. import java.io.*;
  4. class mystruct
  5. {
  6. 	int freq;
  7. 	int data;
  8. 	int start;
  9. 	int end;
  10. }
  11. public class Main
  12. {
  13. 	public static ArrayList<ArrayList<Integer>>pf=new ArrayList<ArrayList<Integer>>();
  14. 	public static int[] arr;
  15. 	public static ArrayList<ArrayList<mystruct>>seg=new ArrayList<ArrayList<mystruct>>();
  16. 	public static int lowsearch(int low,int high,int no,ArrayList<Integer>list)
  17. 	{
  18. 		int mid,j;
  19. 		if(low>high)
  20. 			return -1;
  21. 		else if(list.get(high)<no)
  22. 			return -1;
  23. 		else
  24. 		{
  25. 			mid=(low+high)/2;
  26. 			if(list.get(mid)>=no)
  27. 			{
  28. 				j=lowsearch(low,mid-1,no,list);
  29. 				if(j<mid&&j!=-1)
  30. 					return j;
  31. 				else
  32. 					return mid;
  33. 			}
  34. 			else
  35. 				return lowsearch(mid+1,high,no,list);
  36. 		}
  37. 	}
  38. 	public static int highsearch(int low,int high,int no,ArrayList<Integer>list)
  39. 	{
  40. 		int mid,j;
  41. 		if(low>high)
  42. 			return -1;
  43. 		else if(list.get(low)>no)
  44. 			return -1;
  45. 		else
  46. 		{
  47. 			mid=(low+high)/2;
  48. 			if(list.get(mid)<=no)
  49. 			{
  50. 				j=highsearch(mid+1,high,no,list);
  51. 				if(j>=mid)
  52. 					return j;
  53. 				else
  54. 					return mid;
  55. 			}
  56. 			else
  57. 				return highsearch(low,mid-1,no,list);
  58. 		}
  59. 	}
  60. 	public static void fill(int i,int j,int current,ArrayList<Integer>list,ArrayList<mystruct>ans)
  61. 	{
  62. 		int mid;
  63. 		mystruct node,node1,node2;
  64. 		if(i==j)
  65. 		{
  66. 			node=ans.get(current);
  67. 			node.data=arr[list.get(i)];
  68. 			node.freq=1;
  69. 			node.start=i;
  70. 			node.end=i;
  71. 			return;
  72. 		}
  73. 		else
  74. 		{
  75. 			mid=(i+j)/2;
  76. 			fill(i,mid,2*current+1,list,ans);
  77. 			fill(mid+1,j,2*current+2,list,ans);
  78. 			node=ans.get(current);
  79. 			node1=ans.get(2*current+1);
  80. 			node2=ans.get(2*current+2);
  81. 			if(node1.data>node2.data)
  82. 			{
  83. 				node.data=node1.data;
  84. 				node.freq=node1.freq;
  85. 				node.start=i;
  86. 				node.end=j;
  87. 			}
  88. 			else if(node1.data<node2.data)
  89. 			{
  90. 				node.data=node2.data;
  91. 				node.freq=node2.freq;
  92. 				node.start=i;
  93. 				node.end=j;
  94. 			}
  95. 			else if(node1.data==node2.data)
  96. 			{
  97. 				node.data=node1.data;
  98. 				node.freq=node1.freq+node2.freq;
  99. 				node.start=i;
  100. 				node.end=j;
  101. 			}
  102. 			return  ;
  103. 		}
  104. 	}
  105. 	public static void construct(ArrayList<Integer>list,int current)
  106. 	{
  107. 		int i,k,p;
  108. 		double x,y,z;
  109. 		p=list.size();
  110. 		x=(double)p;
  111. 		y=(double)2;
  112. 		z=Math.log10(x)/Math.log10(y);
  113. 		k=(int)z;
  114. 		y=(double)k;
  115. 		if(y!=z)
  116. 			y++;
  117. 		k=(int)Math.pow((double)2,y+1)-1;
  118. 		ArrayList<mystruct>ans;
  119. 		ans=seg.get(current);
  120. 		mystruct node;
  121. 		for(i=0;i<=k-1;i++)
  122. 		{
  123. 			node=new mystruct();
  124. 			ans.add(node);
  125. 		}
  126. 		fill(0,list.size()-1,0,list,ans);
  127. 		return ;
  128. 	}
  129. 	public static mystruct result(int i,int j,int current,int prime)
  130. 	{
  131. 		mystruct p,q,r;
  132. 		q=new mystruct();
  133. 		int x,y,a,c;
  134. 		p=seg.get(prime).get(current);
  135. 		x=p.start;
  136. 		y=p.end;
  137. 		if(x>=i&&y<=j)
  138. 		{
  139. 			q.data=p.data;
  140. 			q.freq=p.freq;
  141. 			return q;
  142. 		}
  143. 		else if(x>j||y<i)
  144. 		{
  145. 			q.data=-1;
  146. 			q.freq=0;
  147. 			return q;
  148. 		}
  149. 		else
  150. 		{
  151. 			q=result(i,j,2*current+1,prime);
  152. 			r=result(i,j,2*current+2,prime);
  153. 			a=q.data;
  154. 			c=r.data;
  155. 			if(a>c)
  156. 				return q;
  157. 			else if(c>a)
  158. 				return r;
  159. 			else if(c==a)
  160. 			{
  161. 				q.freq=q.freq+r.freq;
  162. 				return q;
  163. 			}
  164. 		}
  165. 		return q;
  166. 	}
  167. 	public static void main(String[] args)
  168. 	throws IOException
  169. 	{
  170. 		Integer i,j,k,l,m,n,p,q,a,b,c;
  171. 		BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
  172. 		String str;
  173. 		String[] string;
  174. 		str=buf.readLine();
  175. 		string=str.split(" ");
  176. 		n=Integer.parseInt(string[0]);
  177. 		m=Integer.parseInt(string[1]);
  178. 		str=buf.readLine();
  179. 		string=str.split(" ");
  180. 		j=string.length;
  181. 		arr=new int[j];
  182. 		for(i=0;i<=j-1;i++)
  183. 			arr[i]=Integer.parseInt(string[i]);
  184. 		//precomputation prime seive
  185. 		int[] primes=new int[100001];
  186. 		primes[0]=1;
  187. 		primes[1]=1;
  188. 		for(i=2;i<=100000;i++)
  189. 		{
  190. 			if(primes[i]==1)
  191. 				continue;
  192. 			else
  193. 			{
  194. 				for(j=2*i;j<=100000;j+=i)
  195. 				{
  196. 					primes[j]=1;
  197. 				}
  198. 			}
  199. 		}
  200. 		ArrayList<Integer>temp;
  201. 		for(i=0;i<=100000;i++)
  202. 		{
  203. 			temp=new ArrayList<Integer>();
  204. 			pf.add(temp);
  205. 		}
  206. 		//prime factorization of the array
  207. 		for(i=0;i<=n-1;i++)
  208. 		{
  209. 			l=arr[i];
  210. 			j=(int)Math.sqrt(l);
  211. 			for(k=1;k<=j;k++)
  212. 			{
  213. 				if(l%k!=0)
  214. 					continue;
  215. 				else
  216. 				{
  217. 					p=l/k;
  218. 					if(p==k)
  219. 					{
  220. 						if(primes[p]==0)
  221. 							pf.get(p).add(i);
  222. 					}
  223. 					else
  224. 					{
  225. 						if(primes[p]==0)
  226. 							pf.get(p).add(i);
  227. 						if(primes[k]==0)
  228. 							pf.get(k).add(i);
  229. 					}
  230. 				}
  231. 			}
  232. 		}
  233. 		//segment tree construction
  234. 		ArrayList<mystruct>temp1;
  235. 		for(i=0;i<=100000;i++)
  236. 		{
  237. 			temp1=new ArrayList<mystruct>();
  238. 			seg.add(temp1);
  239. 		}
  240. 		for(i=0;i<=100000;i++)
  241. 		{
  242. 			if(pf.get(i).size()>0)
  243. 				construct(pf.get(i),i);
  244. 		}
  245. 		ArrayList<Integer>temp2=new ArrayList<Integer>();
  246. 		mystruct help;
  247. 		int x,y;
  248. 		for(i=0;i<=m-1;i++)
  249. 		{
  250. 			p=-1;
  251. 			q=-1;
  252. 			x=-1;
  253. 			y=-1;
  254. 			str=buf.readLine();
  255. 			string=str.split(" ");
  256. 			a=Integer.parseInt(string[0]);
  257. 			b=Integer.parseInt(string[1]);
  258. 			c=Integer.parseInt(string[2]);
  259. 			k=(int)Math.sqrt((double)a);
  260. 			for(j=1;j<=k;j++)
  261. 			{
  262. 				if((a%j)!=0)
  263. 					continue;
  264. 				else
  265. 				{
  266. 					l=a/j;
  267. 					if(l==j)
  268. 					{
  269. 						if(primes[l]==0)
  270. 							temp2.add(l);
  271. 					}
  272. 					else 
  273. 					{
  274. 						if(primes[l]==0)
  275. 							temp2.add(l);
  276. 						if(primes[j]==0)
  277. 							temp2.add(j);
  278. 					}
  279. 				}
  280. 			}
  281. 			//System.out.println(temp2.size());
  282. 			for(j=0;j<=temp2.size()-1;j++)
  283. 			{
  284. 				l=temp2.get(j);
  285. 				temp=pf.get(l);
  286. 				p=lowsearch(0,temp.size()-1,b-1,temp);
  287. 				q=highsearch(0,temp.size()-1,c-1,temp);
  288. 				//System.out.println(p+" "+q);
  289. 				if(p==-1||q==-1)
  290. 				{
  291. 					p=-1;
  292. 					q=-1;
  293. 				}
  294. 				else
  295. 				{
  296. 					help=result(p,q,0,l);
  297. 				    p=help.data;
  298. 				    q=help.freq;
  299. 				}
  300. 				if(p>x)
  301. 				{
  302. 					x=p;
  303. 					y=q;
  304. 				}
  305. 			}
  306. 			temp2.clear();
  307. 			System.out.println(x+" "+y);
  308. 		}
  309. 	}
  310. }
  311.  
Success #stdin #stdout 0.23s 381184KB
comments (?)
stdin
copy 
6 5
1 2 3 4 5 4
2 1 5
121 1 6
3 2 6
5 5 5
24 4 6
stdout
copy 
4 1
-1 -1
3 1
5 1
4 2
https://ideone.com/5EWVUQ
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!