fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  5. #define sim template < class c
  6. #define ris return * this
  7. #define dor > debug & operator <<
  8. #define eni(x) sim > typename \
  9.   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  10. sim > struct rge { c b, e; };
  11. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  12. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  13. sim > char dud(...);
  14. struct debug {
  15. #ifdef LOCAL
  16. ~debug() { cerr << endl; }
  17. eni(!=) cerr << boolalpha << i; ris; }
  18. eni(==) ris << range(begin(i), end(i)); }
  19. sim, class b dor(pair < b, c > d) {
  20.   ris << "(" << d.first << ", " << d.second << ")";
  21. }
  22. sim dor(rge<c> d) {
  23.   *this << "[";
  24.   for (auto it = d.b; it != d.e; ++it)
  25.     *this << ", " + 2 * (it == d.b) << *it;
  26.   ris << "]";
  27. }
  28. #else
  29. sim dor(const c&) { ris; }
  30. #endif
  31. };
  32. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  33. #define         aff(v) for(auto e:v) cout<<e<<" ";cout<<endl;
  34. #define mem1(a)           memset(a,-1,sizeof(a))
  35. #define mem0(a)           memset(a,0,sizeof(a))
  36. #define all(x)            (x).begin(),(x).end()
  37. #define sz(x)             (int)((x).size())
  38. #define yes(check) cout << (check ? "YES" : "NO") << endl
  39. typedef long long ll;
  40. typedef long double ld;
  41. ll n,q,d;
  42. const ll prime=1e9+7;
  43. const ll prime2=998244353;
  44. const ll prime3=7901;
  45.  
  46. const ll MOD = 998244353;
  47. ll INF=2e18;
  48. const int NAX=2e6+5;
  49. vector<int> sieve(NAX);
  50. void init(){
  51. 	for(ll i=2;i<NAX;i++){
  52. 		if(sieve[i]==0){
  53. 			for(ll j=i;j<NAX;j+=i){
  54. 				 sieve[j]=i;
  55. 			}
  56. 		}
  57. 	}
  58. }
  59. const int MAX_N = 2e6+5;
  60. const int LOG = 21;
  61. int a[MAX_N];
  62. int m[MAX_N][LOG]; // m[i][j] is minimum among a[i..i+2^j-1]
  63. int bin_log[MAX_N];
  64. int query(int L, int R) { // O(1)
  65. 	int length = R - L + 1;
  66. 	int k = bin_log[length];
  67. 	return max(m[L][k], m[R-(1<<k)+1][k]);
  68. }
  69.  
  70. void solve(){
  71.  
  72. 	cin >> n >> q;
  73. 	priority_queue<pair<int,int>> pq;
  74. 	bin_log[1] = 0;
  75. 	for(int i = 2; i <= n; i++) {
  76. 		bin_log[i] = bin_log[i/2]+1;
  77. 	}
  78.  
  79. 	for(int i=0;i<n;i++){
  80. 		int va;
  81. 		cin >> va;
  82. 		pq.push({va,-i});
  83. 	}
  84.  
  85. 	int curr=0;
  86.  
  87.  
  88. 	while(!pq.empty()){
  89. 		pair<int,int> p=pq.top();
  90. 		pq.pop();
  91.  
  92. 		int v=p.first;
  93. 		if(v==1){
  94. 			continue;
  95. 		}
  96. 		v=v/sieve[v];
  97. 		curr++;
  98.  
  99. 		m[abs(p.second)][0]=curr;
  100. 		if(v==1){
  101.  
  102. 		}else{
  103. 			pq.push({v,p.second});
  104. 		}
  105. 		//debug() << imie(p) imie(curr) imie(sieve[p.first]) imie(indexes);
  106. 	}
  107.  
  108. for(int k = 1; k < LOG; k++) {
  109. 		for(int i = 0; i + (1 << k) - 1 < n; i++) {
  110. 			m[i][k] = max(m[i][k-1], m[i+(1<<(k-1))][k-1]);
  111. 		}
  112. 	}
  113. 	for(int i=0;i<q;i++){
  114. 		int l,r;
  115. 		cin >> l >> r;
  116. 		l--;r--;
  117. 		cout << query(l,r)<<"\n";
  118.  
  119. 	}
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127. }
  128.  
  129.  
  130.  
  131.  
  132. int main() {
  133. 	fastInp;
  134. 	init();
  135. 	//debug() << imie(s);
  136. 	//freopen("grids.in","r",stdin);
  137. 	//freopen("res.out","w",stdout);
  138. 	// __gcd <long long> (x, y);
  139. 	int tc=1;
  140. 	//debug() << imie(sieve);
  141. 	//cin >> tc;
  142. 	//cout << setprecision(10)<<fixed;
  143.  
  144. 	while(tc--){
  145. 		//i++;
  146. 		//cout <<"Test " << i << ":" << "\n";
  147.  
  148. 		solve();
  149.  
  150. 	}
  151.  
  152. 	return 0;
  153. }
  154.  
  155. /*
  156.    Some insights:
  157.     .Binary search
  158.     .Graph representation
  159.     .Write brute force code
  160.     .Change your approach
  161.  
  162.  
  163.  */
  164.  
  165.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:4: error: illegal character: '#'
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
^
Main.java:4: error: class, interface, or enum expected
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
        ^
Main.java:4: error: class, interface, or enum expected
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
                            ^
Main.java:4: error: class, interface, or enum expected
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
                                         ^
Main.java:5: error: illegal character: '#'
#define sim template < class c
^
Main.java:5: error: class, interface, or enum expected
#define sim template < class c
        ^
Main.java:6: error: illegal character: '#'
#define ris return * this
^
Main.java:7: error: illegal character: '#'
#define dor > debug & operator <<
^
Main.java:8: error: illegal character: '#'
#define eni(x) sim > typename \
^
Main.java:8: error: illegal character: '\'
#define eni(x) sim > typename \
                              ^
Main.java:9: error: > expected
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
                  ^
Main.java:9: error: <identifier> expected
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
                         ^
Main.java:9: error: illegal start of type
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
                          ^
Main.java:10: error: not a statement
sim > struct rge { c b, e; };
    ^
Main.java:10: error: ';' expected
sim > struct rge { c b, e; };
            ^
Main.java:10: error: not a statement
sim > struct rge { c b, e; };
             ^
Main.java:10: error: ';' expected
sim > struct rge { c b, e; };
                ^
Main.java:11: error: ')' expected
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                    ^
Main.java:11: error: not a statement
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
           ^
Main.java:11: error: not a statement
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                     ^
Main.java:11: error: ';' expected
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                      ^
Main.java:11: error: ';' expected
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                           ^
Main.java:11: error: illegal start of expression
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                                            ^
Main.java:11: error: not a statement
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                                             ^
Main.java:11: error: ';' expected
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                                              ^
Main.java:11: error: not a statement
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                                                ^
Main.java:11: error: ';' expected
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
                                                 ^
Main.java:12: error: not a statement
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
    ^
Main.java:12: error: ';' expected
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
          ^
Main.java:12: error: ';' expected
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
                    ^
Main.java:12: error: illegal start of expression
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
                                         ^
Main.java:13: error: '.class' expected
sim > char dud(...);
           ^
Main.java:13: error: not a statement
sim > char dud(...);
    ^
Main.java:13: error: illegal start of expression
sim > char dud(...);
               ^
Main.java:14: error: ';' expected
struct debug {
            ^
Main.java:15: error: illegal character: '#'
#ifdef LOCAL
^
Main.java:15: error: ';' expected
#ifdef LOCAL
            ^
Main.java:16: error: ';' expected
~debug() { cerr << endl; }
        ^
Main.java:16: error: not a statement
~debug() { cerr << endl; }
                ^
Main.java:17: error: illegal start of expression
eni(!=) cerr << boolalpha << i; ris; }
    ^
Main.java:17: error: illegal start of expression
eni(!=) cerr << boolalpha << i; ris; }
      ^
Main.java:17: error: ';' expected
eni(!=) cerr << boolalpha << i; ris; }
       ^
Main.java:17: error: not a statement
eni(!=) cerr << boolalpha << i; ris; }
                          ^
Main.java:17: error: not a statement
eni(!=) cerr << boolalpha << i; ris; }
                                ^
Main.java:18: error: illegal start of expression
eni(==) ris << range(begin(i), end(i)); }
    ^
Main.java:18: error: illegal start of expression
eni(==) ris << range(begin(i), end(i)); }
      ^
Main.java:18: error: ';' expected
eni(==) ris << range(begin(i), end(i)); }
       ^
Main.java:18: error: not a statement
eni(==) ris << range(begin(i), end(i)); }
            ^
Main.java:19: error: <identifier> expected
sim, class b dor(pair < b, c > d) {
   ^
Main.java:19: error: <identifier> expected
sim, class b dor(pair < b, c > d) {
    ^
Main.java:19: error: '{' expected
sim, class b dor(pair < b, c > d) {
            ^
Main.java:19: error: <identifier> expected
sim, class b dor(pair < b, c > d) {
                                ^
Main.java:20: error: not a statement
  ris << "(" << d.first << ", " << d.second << ")";
                                            ^
Main.java:23: error: illegal start of expression
  *this << "[";
  ^
Main.java:23: error: not a statement
  *this << "[";
        ^
Main.java:25: error: illegal start of expression
    *this << ", " + 2 * (it == d.b) << *it;
    ^
Main.java:25: error: illegal start of expression
    *this << ", " + 2 * (it == d.b) << *it;
                                       ^
Main.java:25: error: not a statement
    *this << ", " + 2 * (it == d.b) << *it;
                                    ^
Main.java:26: error: not a statement
  ris << "]";
      ^
Main.java:28: error: illegal character: '#'
#else
^
Main.java:29: error: illegal start of type
sim dor(const c&) { ris; }
        ^
Main.java:29: error: not a statement
sim dor(const c&) { ris; }
                    ^
Main.java:30: error: illegal character: '#'
#endif
^
Main.java:31: error: illegal start of type
};
^
Main.java:32: error: illegal character: '#'
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
^
Main.java:32: error: invalid method declaration; return type required
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
        ^
Main.java:32: error: illegal start of type
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
             ^
Main.java:32: error: <identifier> expected
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
                ^
Main.java:32: error: ';' expected
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
                 ^
Main.java:32: error: illegal character: '#'
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
                          ^
Main.java:33: error: illegal character: '#'
#define         aff(v) for(auto e:v) cout<<e<<" ";cout<<endl;
^
Main.java:33: error: <identifier> expected
#define         aff(v) for(auto e:v) cout<<e<<" ";cout<<endl;
                                                      ^
Main.java:33: error: <identifier> expected
#define         aff(v) for(auto e:v) cout<<e<<" ";cout<<endl;
                                                            ^
Main.java:34: error: illegal character: '#'
#define mem1(a)           memset(a,-1,sizeof(a))
^
Main.java:34: error: invalid method declaration; return type required
#define mem1(a)           memset(a,-1,sizeof(a))
        ^
Main.java:34: error: <identifier> expected
#define mem1(a)           memset(a,-1,sizeof(a))
              ^
Main.java:34: error: ';' expected
#define mem1(a)           memset(a,-1,sizeof(a))
               ^
Main.java:35: error: illegal character: '#'
#define mem0(a)           memset(a,0,sizeof(a))
^
Main.java:36: error: illegal character: '#'
#define all(x)            (x).begin(),(x).end()
^
Main.java:37: error: illegal character: '#'
#define sz(x)             (int)((x).size())
^
Main.java:37: error: <identifier> expected
#define sz(x)             (int)((x).size())
                              ^
Main.java:37: error: <identifier> expected
#define sz(x)             (int)((x).size())
                                  ^
Main.java:37: error: invalid method declaration; return type required
#define sz(x)             (int)((x).size())
                                    ^
Main.java:37: error: ';' expected
#define sz(x)             (int)((x).size())
                                          ^
Main.java:38: error: illegal character: '#'
#define yes(check) cout << (check ? "YES" : "NO") << endl
^
Main.java:39: error: <identifier> expected
typedef long long ll;
            ^
Main.java:40: error: <identifier> expected
typedef long double ld;
       ^
Main.java:40: error: <identifier> expected
typedef long double ld;
            ^
Main.java:42: error: illegal start of type
const ll prime=1e9+7;
^
Main.java:43: error: illegal start of type
const ll prime2=998244353;
^
Main.java:44: error: illegal start of type
const ll prime3=7901;
^
Main.java:46: error: illegal start of type
const ll MOD = 998244353;
^
Main.java:48: error: illegal start of type
const int NAX=2e6+5;
^
Main.java:49: error: <identifier> expected
vector<int> sieve(NAX);
                     ^
Main.java:59: error: illegal start of type
const int MAX_N = 2e6+5;
^
Main.java:60: error: illegal start of type
const int LOG = 21;
^
Main.java:61: error: ']' expected
int a[MAX_N];
      ^
Main.java:61: error: <identifier> expected
int a[MAX_N];
           ^
100 errors
stdout
copy 
Standard output is empty
https://ideone.com/6J3igi
language:
Java (HotSpot 12)
created:
1 year 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!