fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 1e5 + 10;
  5. typedef pair<int,int> pii;
  6. vector<int> Arr, prime[MX], tmp[MX];
  7. int start[MX], fin[MX], val[MX];
  8. pii tree[MX * 10];
  9.  
  10. void sieve(){
  11. 	for(int i = 2; i<MX; i++){
  12. 		if(!prime[i].size()){
  13. 			for(int j = i; j<MX; j += i){
  14. 				prime[j].push_back(i);
  15. 			}
  16. 		}
  17. 	}
  18. }
  19.  
  20. void build(int node, int st, int en){
  21. 	if(st == en){ 
  22. 		tree[node] = pii(val[Arr[st]], 1); 
  23. 	    return;
  24. 	}
  25. 	int l = 2*node, r = l + 1, mid = (st + en)/2;
  26. 	build(l, st, mid);
  27. 	build(r, mid + 1, en);
  28. 	if(tree[l].first > tree[r].first) tree[node] = tree[l];
  29. 	else if(tree[r].first > tree[l].first) tree[node] = tree[r];
  30. 	else{ 
  31. 	  tree[node] = tree[l];
  32. 	  tree[node].second += tree[r].second;
  33. 	}
  34. }
  35.  
  36. pii query(int node, int st, int en, int i, int j){
  37.     if(st > j || en < i) return pii(-1, -1);
  38.     if(st >= i && en <= j) return tree[node];
  39.     int l = 2*node, r = l + 1, mid = (st + en)/2;
  40.     pii p = query(l, st, mid, i, j);
  41.     pii q = query(r, mid + 1, en, i, j);
  42.     if(p.first == -1) return q;
  43.     if(q.first == -1) return p;
  44.  
  45.     if(p.first > q.first) return p;
  46.     if(q.first > p.first) return q;
  47.  
  48.     return pii(p.first, p.second + q.second);
  49. }
  50.  
  51. int main() {
  52. 	int n, m, num, a, b;
  53. 	sieve();
  54. 	scanf("%d %d", &n, &m);
  55. 	memset(start, 0, sizeof(start));
  56. 	memset(fin, 0, sizeof(fin));
  57. 	memset(val, 0, sizeof(val));
  58. 	set<int> S;
  59.  
  60. 	for(int i = 1; i<=n; i++){
  61. 		scanf("%d", &num);
  62. 		val[i - 1] = num;
  63. 		int sz = prime[num].size();
  64.  
  65. 		for(int j = 0; j<sz; j++){
  66. 			int id = prime[num][j];
  67. 			S.insert(id);
  68. 			tmp[id].push_back(i - 1);
  69. 		}
  70. 	}
  71.  
  72. 	set<int>:: iterator it;
  73. 	int st = 0;
  74. 	for(it = S.begin(); it != S.end(); it++){
  75. 		num = (*it);
  76. 		int sz = tmp[num].size();
  77. 		start[num] = st;
  78. 		fin[num] = st + sz - 1;
  79. 		st += sz;
  80.  
  81. 		for(int i = 0; i<sz; i++){
  82. 			int id = tmp[num][i];
  83. 			Arr.push_back(id);
  84. 		}
  85.  
  86. 	}
  87.  
  88. 	build(1, 0, Arr.size() - 1);
  89. 	for(int i = 1; i<=m; i++){
  90. 		int ans = -1, cnt = -1;
  91. 		scanf("%d %d %d", &num, &a, &b); a--, b--;
  92.  
  93. 		int sz = prime[num].size();
  94. 		for(int j = 0; j<sz; j++){
  95. 			int id = prime[num][j];
  96. 			int st = start[id], en = fin[id];
  97. 			if(st == 0 && en == 0) continue;
  98. 			int l = lower_bound(Arr.begin() + st, Arr.begin() + en + 1, a) - Arr.begin();
  99. 			int r = upper_bound(Arr.begin() + st, Arr.begin() + en + 1, b) - Arr.begin();
  100. 			r--;
  101. 			if(l > r) continue;
  102. 			pii p = query(1, 0, Arr.size() - 1, l, r);
  103. 			if(p.first > ans){
  104. 				ans = p.first;
  105. 				cnt = p.second;
  106. 			}
  107. 		}
  108.  
  109. 		printf("%d %d\n", ans, cnt);
  110. 	}
  111. 	return 0;
  112. }
Success #stdin #stdout 0.02s 16920KB
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/TXHpuW
language:
C++14 (gcc 8.3)
created:
8 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!