fork(3) download 
  1. #include<stdio.h>
  2. #include<vector>
  3. # include<algorithm>
  4. using namespace std;
  5. #define limit 1000009
  6. vector<int> sieve[limit];
  7. vector<int> b[limit],freq[limit];
  8. vector<vector<int> >cc[limit];
  9. int a[limit];
  10. int main()
  11. {
  12.     int i,j,k,c,G,x,y,m,n;
  13.     //prime factorisation
  14.     for(i=2;i*i<limit;i++)
  15.         if(sieve[i].size()==0)
  16.             for(j=i;j<limit;j+=i)
  17.                 sieve[j].push_back(i);
  18.     //done
  19.     scanf("%d %d",&n,&m);
  20.     for(i=1;i<=n;i++)
  21.     {
  22.         scanf("%d",&c);
  23.         a[i]=c;
  24.         freq[c].push_back(i);
  25.         int sz=sieve[c].size();
  26.         for(k=0;k<sz;k++)
  27.         {
  28.             b[sieve[a[i]][k]].push_back(i);
  29.             while(c%sieve[a[i]][k]==0)c=c/sieve[a[i]][k];
  30.         }
  31.         if(c>1)b[c].push_back(i);
  32.     }
  33.     //implementing RMQ
  34.         for(i=0;i<limit;i++)
  35.         {
  36.         	int sz=b[i].size();
  37.         	if(!sz)continue;
  38.         	int level=0;
  39.         	cc[i].resize(sz);
  40.         	for(j=0;j<sz;j++)cc[i][j].push_back(b[i][j]);//level 0
  41.         	for(level=1;(1<<level)<=sz;level++)
  42.         	{
  43.             	for(j=0;j+(1<<level)<=sz;j++)
  44.             	{
  45.             	 int c1=cc[i][j][level-1];
  46.             	 int c2=cc[i][j+(1<<(level-1))][level-1];
  47.             	 int mx=(a[c1]<a[c2])?c2:c1;
  48.             	 cc[i][j].push_back(mx);
  49.         	 	}
  50.         	}
  51. 	}
  52. 	//RMQ vector 'cc' has been made 
  53. for(i=1;i<=m;i++)
  54.     {
  55.         scanf("%d %d %d",&G,&x,&y);
  56.         int maxx=-1,ct=-1,factor,mct=-1;
  57.         c=G;
  58.         int sz=sieve[c].size();
  59.         for(k=0;k<=sz;k++)
  60.         {   //it would run for all the prime factors of G
  61.             ct=-1;
  62.             if(k==sz)
  63.             {
  64.                 if(c>1)factor=c;
  65.                 else continue;
  66.             }
  67.             else factor=sieve[G][k];
  68.             if(k!=sz)while(c%sieve[G][k]==0)c=c/sieve[G][k];
  69.             int sz2=b[factor].size();
  70.             if(!sz2)continue;
  71.             //find ans using RMQ
  72.             	int lb,ub;
  73.             	lb=lower_bound(b[factor].begin(),b[factor].end(),x)-b[factor].begin();
  74.             	ub=upper_bound(b[factor].begin(),b[factor].end(),y)-b[factor].begin();
  75.             	if(lb>=ub)break;
  76.             	ub--;
  77.             	int xxx=0;
  78.             	while(lb+(1<<xxx)-1<ub)xxx++;
  79.             	if(lb+(1<<xxx)-1>ub)xxx--;
  80.             	int c11=cc[factor][lb][xxx];
  81.             	int c22=cc[factor][ub-(1<<xxx)+1][xxx];
  82.             	ct=(a[c11]<a[c22])?c22:c11;
  83.             //RMQ has given the index in 'ct'
  84.             if(mct==-1)mct=ct;
  85. 			else
  86. 			if(ct!=-1)
  87. 			if(a[ct]>a[mct])mct=ct;
  88.             }
  89.             if(mct!=-1)
  90.         {
  91.         //getting the Frequency
  92.             int lb,ub;
  93.             int a2,ff=a[mct];
  94.             lb=lower_bound(freq[ff].begin(),freq[ff].end(),x)-freq[ff].begin();
  95.             ub=upper_bound(freq[ff].begin(),freq[ff].end(),y)-freq[ff].begin();
  96.             printf("%d %d\n",a[mct],ub-lb);
  97.         }
  98.         else printf("-1 -1\n");
  99.     }
  100.     return 0;
  101. }
Success #stdin #stdout 0.53s 73536KB
comments (?)
stdin 
35 7
123 324 43 456  2 12 34 456 54 7654 4 234 436 56 3 1  43 34 456 56 32 436 456 21 436 12233 10100 312 234 456 10101 12345 432 1 12
12 1 32
11 1 15
12 19 22
12 7 7
23 5 25
10101 1 35
101 1 35
stdout 
12345 1
-1 -1
456 1
34 1
-1 -1
12345 1
10100 1
https://ideone.com/ut4Ikj
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!