fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<math.h>
  7. #include<limits.h>
  8. #include<list>
  9. #define lli long long int
  10. #define mod 1000000007
  11. using namespace std;
  12. lli N,K,Q;
  13. lli arr[10000009];
  14. lli ans[10000009];
  15. lli a,b,c,d,e,f,r,s,t,m;
  16. lli L1,La,Lc,Lm,D1,Da,Dc,Dm;
  17. lli pow_t[100000009];
  18. void power_t(lli n)
  19. {
  20.    pow_t[0]=1%s;
  21.    for(lli i=1;i<n+3;i++)
  22.    {
  23.      pow_t[i]=pow_t[i-1]*t;
  24.      pow_t[i]=pow_t[i]%s;
  25.    }
  26. }
  27. lli generate_arr()
  28. {
  29.   power_t(N);
  30.   for(lli x=2;x<=N;x++)
  31.   {
  32.     if(pow_t[x]%s<=r)
  33.        arr[x]=(  ( ( ((a*arr[x-1])%m) *arr[x-1] )%m  +  (b*arr[x-1])%m )%m +c)%m;
  34.     else
  35.        arr[x]=(  ( ( ((d*arr[x-1])%m) *arr[x-1] )%m  +  (e*arr[x-1])%m )%m +f)%m;
  36.        //arr[x]=(d*arr[x-1]*arr[x-1]+e*arr[x-1]+f)%m;
  37.   }
  38.   for(lli x=0;x<N;x++)
  39.   {
  40.     arr[x]=arr[x+1];
  41.   }
  42. }
  43.  
  44.  
  45. void fun()
  46. {
  47.    //lli arr[]={4,3,2,1};
  48.    //lli len=sizeof(arr)/sizeof(lli);
  49.    lli len=N;
  50.    list<lli> p;
  51.    p.clear();
  52.    lli k=K;
  53.    for(lli i=0;i<len;i++)
  54.    {
  55.        if(i>=k)
  56.          ans[i-k]=p.front();
  57.        while(!p.empty()  && p.back()>arr[i])
  58.          p.pop_back();
  59.        p.push_back(arr[i]);
  60.       if(i>=k && arr[i-k]==p.front()){
  61.          p.pop_front();
  62.       }
  63.    }
  64.    lli min1=LONG_LONG_MAX;
  65.    for(lli i=len-k;i<len;i++)
  66.    {
  67.       if(min1>arr[i])
  68.         min1=arr[i];
  69.    }
  70.    for(lli i=len-k;i<len;i++)
  71.    {
  72.         ans[i]=min1;
  73.    }
  74.  
  75.  /* printf("ans \n");
  76.    for(lli i=0;i<len;i++)
  77.    {
  78.       printf("%lld ",ans[i]);
  79.    }
  80.    printf("ans\n");*/
  81. }
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98. lli query(lli qs,lli qe)
  99. {
  100.   return min(ans[qs],ans[qe-K+1]);
  101. }
  102.  
  103.  
  104. void generate_range()
  105. {
  106.    //lli * tree=csum();
  107.    lli sum=0;
  108.    lli prdct=1;
  109.    fun();
  110.    for(lli i=1;i<=Q;i++)
  111.    {
  112.       L1=(La*L1+Lc)%Lm;
  113.       D1=(Da*D1+Dc)%Dm;
  114.       //printf("D1=%lld\n",D1);
  115.       lli L=L1+1;
  116.       lli R=min(L+K-1+D1,N);
  117.       //printf("L===%lld R====%lld\n",L,R);
  118.       lli qs=L-1;
  119.       lli qe=R-1;
  120.  
  121.       lli zuck;
  122.       zuck=query(qs,qe);
  123.       sum=sum+zuck;
  124.       prdct=(prdct*zuck)%mod;
  125.    }
  126.    printf("%lld %lld\n",sum,prdct%mod);
  127. }
  128.  
  129. int main()
  130. {
  131.    scanf("%lld%lld%lld",&N,&K,&Q);
  132.    scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",
  133.    &a,&b,&c,&d,&e,&f,&r,&s,&t,&m,&arr[1]);
  134.    scanf("%lld%lld%lld%lld%lld%lld%lld%lld",
  135.    &L1,&La,&Lc,&Lm,&D1,&Da,&Dc,&Dm);
  136.    generate_arr();
  137.   /* for(lli i=0;i<N;i++)
  138.      printf("%lld ",arr[i]);*/
  139.  
  140.    generate_range();
  141.    return 0;
  142. }
  143.  
Runtime error #stdin #stdout 0s 940544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rkAgT2
language:
C++ (gcc 8.3)
created:
8 years 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!