fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp> 
  3. #include<ext/pb_ds/tree_policy.hpp> 
  4. using namespace std;
  5. void __print(int x) {cerr << x;}
  6. void __print(long x) {cerr << x;}
  7. void __print(long long x) {cerr << x;}
  8. void __print(unsigned x) {cerr << x;}
  9. void __print(unsigned long x) {cerr << x;}
  10. void __print(unsigned long long x) {cerr << x;}
  11. void __print(float x) {cerr << x;}
  12. void __print(double x) {cerr << x;}
  13. void __print(long double x) {cerr << x;}
  14. void __print(char x) {cerr << '\'' << x << '\'';}
  15. void __print(const char *x) {cerr << '\"' << x << '\"';}
  16. void __print(const string &x) {cerr << '\"' << x << '\"';}
  17. void __print(bool x) {cerr << (x ? "true" : "false");}
  18.  
  19. template<typename T, typename V>
  20. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  21. template<typename T>
  22. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  23. void _print() {cerr << "]\n";}
  24. template <typename T, typename... V>
  25. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  26. #ifndef ONLINE_JUDGE
  27. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  28. #else
  29. #define debug(x...)
  30. #endif
  31. #define endl '\n'
  32. #define ll long long int
  33. #define md 1000000007
  34. #define MP make_pair
  35. #define pb push_back
  36. #define ppb pop_back
  37.  
  38.  
  39. const ll INF=1e9+15;
  40. const ll NAX= 1e5+5; // change it acc tothe contraints
  41.  
  42.  
  43. vector<ll> arr(NAX);
  44.  
  45.  
  46. struct node{
  47.     int num=0;
  48.     int cnt=1;
  49.   /*  node(){
  50.         num=0;
  51.         cnt=0;
  52.         _gcd=0;
  53.     }
  54.     node (int val){
  55.         num=val;
  56.     }
  57.  
  58.     void merge(node &root, node &left, node& right){
  59.         _gcd=gcd();
  60.     }
  61.     */
  62. };
  63.  
  64. node null_n;
  65. //node tree[4*NAX];
  66. vector<node> tree;
  67.  
  68. int gcd(int a,int b)
  69. {
  70.     {int t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
  71. }
  72.  
  73. void merge(node &root,  node &left,  node &right){
  74.     int gcd_num=gcd(left.num, right.num);
  75.     root.num=gcd_num;
  76.     int cnt_now=0;
  77.     debug(root.cnt, root.num, gcd_num);
  78.     if(left.num==gcd_num){
  79.         cnt_now+=left.cnt;
  80.         //cnt_now+=1;
  81.         root.cnt=cnt_now;
  82.     }
  83.     if(right.num==gcd_num){
  84.         cnt_now+=right.cnt;
  85.         //cnt_now+=1;
  86.         root.cnt=cnt_now;
  87.     }
  88.     debug(root.num,left.num, right.num, root.cnt, left.cnt, right.cnt);
  89. }
  90.  
  91. void build(ll si, ll ss,ll se){
  92.     if(ss==se){
  93.         tree[si].cnt=0;
  94.         tree[si].num=arr[ss];
  95.         return;
  96.     }
  97.  
  98.  
  99.  
  100.     int mid=(ss+se)/2;
  101.     int lc=2*si;
  102.     int rc=2*si+1;
  103.     build(2*si, ss,mid);
  104.     build(2*si+1, mid+1,se);
  105.     merge(tree[si],tree[lc],tree[rc]);     
  106.  
  107.  
  108.     //tree[si]=__gcd(tree[lc], tree[rc]);
  109.    //debug(tree[si].open_need, tree[si].close_need, tree[si].len);
  110. }
  111.  
  112. void printTree(int i,int l,int r){
  113.     cout<<"id= "<<i<<" "<<"num: "<<tree[i].num<<" "<<"count: "<<tree[i].cnt<<endl;
  114.         //<<" "<<"clse_need: "<<tree[i].close_need<<endl;
  115.     if(l==r){
  116.         return;
  117.     }
  118.  
  119.     int mid = (l+r)/2 ;
  120.     int left = i*2,right = i*2+1;
  121.     printTree(left,l,mid);
  122.     printTree(right,mid+1,r);
  123. }
  124.  
  125.  
  126. node query(ll root,ll  node_low, ll node_high, ll  query_low, ll query_high){
  127.     if(node_low>=query_low and query_high>=node_high){
  128.       return tree[root]; 
  129.     }    
  130.  
  131.     if(query_low>node_high or node_low>query_high){
  132.         return null_n;
  133.     }
  134.     node ans;
  135.      ll mid=(node_low+node_high)/2;
  136.   node lc=query(2*root, node_low, mid, query_low, query_high);
  137.  
  138.   node rc=query(2*root+1, mid+1, node_high, query_low, query_high);
  139.     merge(ans, lc, rc);
  140.     return ans;
  141. }
  142. /*void update(ll root, ll node_low, ll node_high, ll query_low, ll query_high, ll val){
  143.     if(node_low>=query_low and query_high>=node_high){
  144.         tree[root]=val;
  145.         return;
  146.     }
  147.     if(query_low>node_high or node_low>query_high){
  148.         return ;
  149.     }
  150.     ll mid=(node_low+node_high)/2;
  151.      update(2*root, node_low, mid, query_low, query_high, val);
  152.      update(2*root+1, mid+1, node_high, query_low, query_high, val);
  153.      tree[root]=__gcd(tree[2*root],tree[2*root+1]);
  154. }
  155.  */
  156. void solve()
  157. {
  158.    ll n, q;
  159.    cin>>n;
  160.    for(int i=0; i<n; i++){
  161.        cin>>arr[i];
  162.    }
  163.    /* while(__builtin_popcount(n)!=1){
  164.       arr.pb(0);
  165.       n++;
  166.     }
  167.     */
  168.     tree.resize(4*NAX);
  169.     cin>>q;
  170.     build(1,0,n-1);
  171.     printTree(1,0,n-1);
  172.     while(q--){
  173.         ll l,r;
  174.         cin>>l>>r;
  175.         l--;
  176.         r--;
  177.     //debug(tree[0]);
  178.      //   cout<<2*query(1,0,n-1, l,r).len<<endl;
  179.         ll no_ant=0;
  180.          no_ant=r-l;
  181.         ll answer=0;
  182.         ll cnt_now=query(1,0,n-1,l,r).cnt;
  183.         if(cnt_now==no_ant)answer+=1;
  184.         cout<<no_ant-answer<<endl;
  185.         debug(no_ant, answer, cnt_now);
  186.     }   
  187.  
  188.  
  189.  
  190.  
  191. }
  192. int main() {
  193.  
  194.  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  195.  
  196. int tc=1;
  197.    // cin>>tc;
  198.     for (int i=0; i<tc; i++){
  199. 		solve();
  200. 		//cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  201.  
  202. 		}
  203.  
  204.  
  205.  
  206. }
  207.  
  208.  
Time limit exceeded #stdin #stdout 5s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SD1Zmh
language:
C++ (gcc 8.3)
created:
2 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!