fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define lb lower_bound
  3. #define pii pair<int,int>
  4. #define fi first
  5.  
  6. #define int long long
  7. #define se second
  8. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  9. #define op freopen
  10. #define sz size
  11. #define TXT "test"
  12. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  13.  
  14. using namespace std;
  15.  
  16. int n,a[100006],b[100006],q,st[100006][18];
  17. void setup()
  18. {
  19.     for(int i=1;i<=n;i++)
  20.     {
  21.         st[i][0]=a[i];
  22.     }
  23.     for(int j=1;(1<<j)<=n;j++)
  24.     {
  25.         for(int i=1;i+(1<<j)-1<=n;i++)
  26.         {
  27.             st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
  28.         }
  29.     }
  30. }
  31. int get(int l,int r)
  32. {
  33.     int j=log2(r-l+1);
  34.     return __gcd(st[l][j],st[r-(1<<j)+1][j]);
  35. }
  36. main()
  37. {
  38.     ios;
  39.     freo;
  40.     cin>>n>>q;
  41.     for(int i=1;i<=n;i++)
  42.     {
  43.         cin>>a[i];
  44.     }
  45.     for(int i=1;i<=n;i-=-1)
  46.     {
  47.         cin>>b[i];
  48.         a[i]=abs(a[i]-b[i]);
  49.     }
  50.     setup();
  51.     while(q--)
  52.     {
  53.         int l,r;
  54.         cin>>l>>r;
  55.         cout<<get(l,r)<<"\n";
  56.     }
  57. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3 2
0 0 0
4 6 9
1 2 
2 3
stdout
copy 
2
3
https://ideone.com/2fL1KJ
language:
C++ (gcc 8.3)
created:
14 days 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!