fork download
copy 
  1. //codechef CHEFCK
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #ifndef ONLINE_JUDGE
  6. 	#define LOCAL_JUDGE
  7. #endif
  8. //#define sc(x) scanf("%lld",&x)
  9. #define mod 1000000007ll
  10. typedef long long lo;
  11. lo arr[10000009];
  12. int st[18][10000009];
  13.  
  14. inline void sc(long long int &x){
  15.     register long long int c = getchar_unlocked();
  16.     x = 0;
  17.     long long int neg = 0;
  18.     for(;((c<48 || c>57) && c != '-');c = getchar_unlocked());
  19.     if(c=='-') {neg=1;c=getchar_unlocked();}
  20.     for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c - 48;}
  21.     if(neg) x=-x;
  22. }
  23.  
  24. lo rmq(lo x,lo y){
  25. 	int k=log2(y-x+1);
  26. 	if(arr[st[k][x]]<=arr[st[k][y-(1<<k)+1]])
  27. 		return arr[st[k][x]];
  28. 	else
  29. 		return arr[st[k][y-(1<<k)+1]];
  30. 	}
  31. lo powa(lo x,lo y,lo modi){
  32. 	if(y==0)return 1;
  33. 	long long res=1;
  34. 	long long cur=x; 
  35. 	while(y){
  36.   		if(y%2){
  37. 		res=(res*cur)%modi;
  38. 		}
  39. 		y/=2;
  40. 		cur=(cur*cur) % modi;
  41. 		}
  42. 	return res;
  43. 	}
  44.  
  45.  
  46. int main(){
  47. 	ios_base::sync_with_stdio(0);
  48. 	lo N,K,Q;
  49. 	lo a,b,c,d,e,f,r,s,t,m;
  50. 	scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",&N,&K,&Q,&a,&b,&c,&d,&e,&f,&r,&s,&t,&m,&arr[1]);
  51. 	//sc(N);sc(K);sc(Q);
  52. 	//sc(a);sc(b);sc(c);sc(d);sc(e);sc(f);sc(r);sc(s);sc(t);sc(m);sc(arr[1]);
  53.  
  54. 	lo x;
  55. 	for(x=2;x<=N;x++){
  56. 		if(powa(t,x,s) <= r)
  57. 			arr[x]=((a%m)*(arr[x-1]*arr[x-1])%m+(b*arr[x-1])%m+c+m)%m;
  58. 		else 
  59. 			arr[x]=((d%m)*(arr[x-1]*arr[x-1])%m+(e*arr[x-1])%m+f+m)%m;
  60. 		}
  61.  
  62. 	lo i,j;
  63. 	for(i=0;i<N+1;i++)st[0][i]=i;
  64. 	for(j=2;(1<<j)<=N;j++)
  65. 		for(i=1;i+(1<<j)-1<=N;i++){
  66. 			if(arr[st[j-1][i]]<arr[st[j-1][i+(1<<(j-1))]])
  67. 				st[j][i]=st[j-1][i];
  68. 			else
  69. 				st[j][i]=st[j-1][i+(1<<(j-1))];
  70. 			}
  71. 	//for(i=1;i<=N;i++)cout<<arr[i]<<" ";
  72. 	lo L1,La,Lc,Lm,D1,Da,Dc,Dm;
  73. 	sc(L1);sc(La);sc(Lc);sc(Lm);
  74. 	sc(D1);sc(Da);sc(Dc);sc(Dm);
  75.  
  76.  
  77. 	lo L,R,temp,sum=0,pro=1;
  78. 	for(i=1;i<=Q;i++){
  79. 		L1=(La * L1 +Lc)%Lm;
  80. 		D1=(Da * D1 +Dc)%Dm;
  81. 		L=L1+1;
  82. 		R=min(L+K-1+D1,N);
  83. 		if(L>R)swap(L,R);
  84. 		if(K<=R-L+1&&R-L+1<=2*K){
  85. 			temp=rmq(L,R);
  86. 			sum=(sum+temp);
  87. 			pro=(pro*temp+mod)%mod;
  88. 			}
  89. 		}
  90. 	printf("%lld %lld\n",sum,pro);
  91.  
  92. 	return 0;
  93. 	}
  94.  
Time limit exceeded #stdin #stdout 5s 784384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EwvZF5
language:
C++14 (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!