fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define lb lower_bound
  4. #define ub upper_bound
  5. #define pii pair<int,int>
  6. #define fi first
  7. #define int long long
  8. #define se second
  9. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  10. #define TXT "test"
  11. #define freo if(fopen(TXT".inp","r")){freopen(TXT".inp","r",stdin); freopen(TXT".out","w",stdout);}
  12.  
  13. using namespace std;
  14.  
  15. const int INF = 0x3f3f3f3f3f3f3f3fLL;
  16. const int MXN = 2*1e5+5;
  17. int n,m,a[MXN],pa[MXN][19];
  18. void build()
  19. {
  20.     for(int i=1;i<=n;i++)
  21.         pa[i][0]=a[i];
  22.     for(int j=1;j<=log2(n);j++)
  23.     {
  24.         for(int i=1;i<=(n-(1<<j)+1);i++)
  25.         {
  26.             pa[i][j] = min(pa[i][j - 1], pa[i + (1 << (j - 1))][j - 1]);
  27.         }
  28.     }
  29. }
  30. int get(int l,int r)
  31. {
  32.     int k=log2(r-l+1);
  33.     return min(pa[l][k],pa[r-(1<<k)+1][k]);
  34. }
  35.  
  36. int bs(int l,int r,int cost)
  37. {
  38.     int m,ans=-1;
  39.     while(l<=r)
  40.     {
  41.         m=(l+r)>>1;
  42.         if(get(l,m)>cost)
  43.         {
  44.             l=m+1;
  45.         }
  46.         else
  47.         {
  48.             r=m-1;
  49.             ans=m;
  50.         }
  51.     }
  52.     return ans;
  53. }
  54.  
  55. void solve()
  56. {
  57.     cin>>n>>m;
  58.     for(int i=1;i<=n;i++)
  59.     {
  60.         cin>>a[i];
  61.     }
  62.     build();
  63.     int cost,l,r;
  64.     while(m--)
  65.     {
  66.         cin>>cost>>l>>r;
  67.         while(cost>0)
  68.         {
  69.             int d=bs(l,r,cost);
  70.             if(d==-1)
  71.                 break;
  72.             cost%=a[d];
  73.         }
  74.         cout<<cost<<"\n";
  75.     }
  76. }
  77.  
  78. int32_t main()
  79. {
  80.     ios;
  81.     freo;
  82.     solve();
  83. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Jrbcmk
language:
C++ (gcc 8.3)
created:
7 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!