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==root.num and left.num!=0){
  79.         root.cnt+=left.cnt;
  80.        // cnt_now+=1;
  81.         /*
  82.          * root.cnt+=cnt_now;
  83.          * */
  84.     }
  85.     else if(right.num==root.num and right.num!=0){
  86.         root.cnt+=right.cnt;
  87.        //cnt_now+=1;
  88.        // root.cnt+=cnt_now;
  89.     }
  90.     else{
  91.         root.cnt=0;
  92.     }
  93.  
  94.  debug(root.num,left.num, right.num, root.cnt, left.cnt, right.cnt);
  95. }
  96.  
  97. void build(ll si, ll ss,ll se){
  98.     if(ss==se){
  99.         tree[si].cnt=1;
  100.         tree[si].num=arr[ss];
  101.         //debug(arr[ss]);
  102.         return;
  103.     }
  104.  
  105.  
  106.  
  107.     int mid=(ss+se)/2;
  108.     int lc=2*si;
  109.     int rc=2*si+1;
  110.     build(2*si, ss,mid);
  111.     build(2*si+1, mid+1,se);
  112.     merge(tree[si],tree[lc],tree[rc]);     
  113.  
  114.  
  115.     //tree[si]=__gcd(tree[lc], tree[rc]);
  116.    //debug(tree[si].cnt, tree[si].num, lc, rc);
  117. }
  118.  
  119. void printTree(int i,int l,int r){
  120.     cout<<"id= "<<i<<" "<<"num: "<<tree[i].num<<" "<<"count: "<<tree[i].cnt<<endl;
  121.         //<<" "<<"clse_need: "<<tree[i].close_need<<endl;
  122.     if(l==r){
  123.         return;
  124.     }
  125.  
  126.     int mid = (l+r)/2 ;
  127.     int left = i*2,right = i*2+1;
  128.     printTree(left,l,mid);
  129.     printTree(right,mid+1,r);
  130. }
  131.  
  132.  
  133. node query(ll root,ll  node_low, ll node_high, ll  query_low, ll query_high){
  134.     if(node_low>=query_low and query_high>=node_high){
  135.       return tree[root]; 
  136.     }    
  137.  
  138.     if(query_low>node_high or node_low>query_high){
  139.         return null_n;
  140.     }
  141.     node ans;
  142.      ll mid=(node_low+node_high)/2;
  143.   node lc=query(2*root, node_low, mid, query_low, query_high);
  144.  
  145.   node rc=query(2*root+1, mid+1, node_high, query_low, query_high);
  146.     merge(ans, lc, rc);
  147.     debug(lc.num, lc.cnt, rc.num, rc.cnt,ans.num, ans.cnt);
  148.     return ans;
  149. }
  150. /*void update(ll root, ll node_low, ll node_high, ll query_low, ll query_high, ll val){
  151.     if(node_low>=query_low and query_high>=node_high){
  152.         tree[root]=val;
  153.         return;
  154.     }
  155.     if(query_low>node_high or node_low>query_high){
  156.         return ;
  157.     }
  158.     ll mid=(node_low+node_high)/2;
  159.      update(2*root, node_low, mid, query_low, query_high, val);
  160.      update(2*root+1, mid+1, node_high, query_low, query_high, val);
  161.      tree[root]=__gcd(tree[2*root],tree[2*root+1]);
  162. }
  163.  */
  164. void solve()
  165. {
  166.    ll n, q;
  167.    cin>>n;
  168.    for(int i=0; i<n; i++){
  169.        cin>>arr[i];
  170.    }
  171.    /* while(__builtin_popcount(n)!=1){
  172.       arr.pb(0);
  173.       n++;
  174.     }
  175.     */
  176.     tree.resize(4*NAX);
  177.     cin>>q;
  178.     build(1,0,n-1);
  179.     cout<<"BEfore: "<<endl;
  180.     printTree(1,0,n-1);
  181.     while(q--){
  182.         ll l,r;
  183.         cin>>l>>r;
  184.         l--;
  185.         r--;
  186.     //debug(tree[0]);
  187.      //   cout<<2*query(1,0,n-1, l,r).len<<endl;
  188.         ll no_ant=0;
  189.          no_ant=r-l+1;
  190.         ll answer=0;
  191.         ll cnt_now=query(1,0,n-1,l,r).cnt;
  192.         if(cnt_now==no_ant-1)answer+=1;
  193.         cout<<no_ant-answer<<endl;
  194.         debug(no_ant, answer, cnt_now);
  195.     }   
  196.  
  197.  
  198.  
  199. }
  200. int main() {
  201.  
  202.  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  203.  
  204. int tc=1;
  205.    // cin>>tc;
  206.     for (int i=0; i<tc; i++){
  207. 		solve();
  208. 		//cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  209.  
  210. 		}
  211.  
  212.  
  213.  
  214. }
  215.  
  216.  
Time limit exceeded #stdin #stdout 5s 5396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Xi6t93
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!