fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n,m,x,y;
  5. ll mod=1000000007;
  6. int a[1000010];
  7. ll s[1000010];
  8.  
  9. ll power(ll a, ll b){
  10. 	if(b==0)
  11. 		return 1;
  12. 	ll t=power(a,b/2);
  13. 	t=(t*t)%mod;
  14. 	if(b%2)
  15. 		return (a*t)%mod;
  16. 	return t%mod;
  17. }
  18.  
  19. ll coeff(ll a){
  20. 	return ((power(3,a)+1)%mod*power(2,mod-2))%mod;
  21. }
  22.  
  23. ll query(ll s,ll e,ll x,ll y,ll lval,ll rval, ll t){ //cout<<t<<" - "<<s<<" "<<e<<endl;
  24. 	if(s>e || s>y || e<x || t>m+3){
  25. 		return 0;
  26. 	}	
  27. 	if(e-s==1){
  28. 		if(s>=x && e<=y){ 			
  29. 			return (coeff(m-t)*(lval+rval)%mod)%mod;
  30. 		}
  31. 		if(s==x)
  32. 			return lval%mod;
  33. 		else
  34. 			return rval%mod;
  35.  
  36. 	}
  37. 	if(s>=x && e<=y){ //cout<<t<<" - "<<s<<" "<<e<<" "<<(coeff(m-t)*(lval+rval))%mod<<endl;
  38. 		return (coeff(m-t)*(lval+rval)%mod)%mod;
  39. 	}	
  40. 	ll mid=(s+e)/2,sub1=0,sub2=0,sub=0;
  41. 	sub1=query(s,mid,x,y,lval,(lval+rval)%mod,t+1); 
  42. 	//cout<<t<<" sub1- "<<s<<" "<<mid<<" "<<sub1<<endl;
  43. 	if(y>=1+mid)
  44. 		sub2=query(mid,e,x,y,(lval+rval)%mod,rval,t+1);		
  45. 	//cout<<t<<" sub2- "<<mid<<" "<<e<<" "<<sub2<<endl;
  46. 	sub=(sub1+sub2)%mod;
  47. 	if(sub1>0 && sub2>0){
  48. 		sub=(mod+sub-lval)%mod;
  49. 		sub=(mod+sub-rval)%mod;
  50. 	}
  51. 	//cout<<t<<" sub- "<<s<<" "<<e<<" "<<sub<<endl;
  52. 	return sub%mod;
  53.  
  54. }
  55.  
  56. int main(){
  57. 	int t;
  58. 	cin>>t;
  59. 	while(t--){
  60. 		scanf("%lld %lld %lld %lld",&n,&m,&x,&y);
  61. 		for(int i=1;i<=n;i++){
  62. 			scanf("%d",&a[i]);
  63. 		}
  64. 		s[0]=a[0]=0;
  65. 		s[1]=a[1];
  66. 		for(int i=2;i<=n;i++){
  67. 			s[i]=(s[i-1]+a[i])%mod;
  68. 			//cout<<s[i]<<" ";
  69. 		}		
  70. 		ll x1,y1;
  71. 		x1 = 1+(x-1.0)/power(2,m);
  72. 		y1 = 1+ceil((y-1.0)*1.0/power(2,m));		
  73. 		ll t0,t1,t2;
  74. 		t0=(s[y1]-s[x1-1]+mod)%mod;
  75. 		//cout<<t0<<endl;
  76. 		t1=(t0*2)%mod;
  77. 		t1=(t1-a[y1]+mod)%mod;
  78. 		t1=(t1-a[x1]+mod)%mod;
  79. 		t1=(t1*coeff(m))%mod;		
  80. 		t2=(t0-a[x1]+mod)%mod;
  81. 		t2=(t2-a[y1]+mod)%mod;
  82. 		//cout<<t2<<endl;
  83. 		ll sum;
  84. 		sum=(mod+t1-t2)%mod;
  85. 		//cout<<"Hola "<<sum<<endl;
  86. 		ll limit=1+power(2,m)*(x1-1);
  87. 		sum=(mod+sum-query(limit,limit+power(2,m),limit,x-1,a[x1],a[x1+1],0))%mod;
  88. 		//cout<<sub<<endl;
  89. 		limit=1+power(2,m)*(y1-1);
  90. 		sum=(mod+sum-query(limit-power(2,m),limit,y+1,limit,a[y1-1],a[y1],0))%mod;
  91. 		//cout<<sub<<endl;
  92.  
  93. 		printf("%lld\n",(sum)%mod);
  94. 	}
  95. 	return 0;
  96. }
Success #stdin #stdout 0s 15184KB
comments (?)
stdin
copy 
1
250 20 1040 1400
46064 66844 38598 69247 3054 83290 95827 78193 36667 61330 33947 88682 40166 56508 13601 35658 92261 16213 6257 61509 96764 65 68349 35399 47081 7260 24967 44152 33715 82451 47249 31955 24960 51315 62532 20878 81101 20126 71579 78754 6212 40422 12786 83892 40037 20300 10642 50958 83688 48898 67434 88268 8020 87473 10288 72078 17899 69583 72569 33960 83611 57921 22932 24481 46730 1415 31011 78447 93771 97653 78673 10810 54597 92823 89325 23135 53808 45498 50919 87983 42752 36881 55859 43915 86695 44142 69246 76952 85203 82486 15579 93732 93969 76160 92462 38747 96861 92339 99238 59097 11808 41375 15360 62107 88710 25687 62239 10597 89802 66514 46354 12340 63057 85212 22065 73305 16621 23191 33367 8387 43887 71869 83027 11382 2093 36395 79691 42489 48688 50971 48727 98918 78766 72611 87095 99364 34006 91162 33370 42574 93203 73289 97106 87436 51585 8658 64584 33691 79444 85516 38468 92708 1514 64822 49248 95112 13295 22962 58798 41648 78781 76472 73476 54856 54380 21818 58466 21421 2211 88343 76580 80245 25145 26680 9711 63628 15542 52624 98800 76277 87625 32136 72824 43364 36199 58795 54421 909 57905 78450 4421 54525 15238 20046 89225 7747 48084 22606 60653 89110 55777 87872 10227 86059 47610 36719 25902 3139 6630 76831 13818 52202 69400 51524 49006 91759 42393 32673 88902 12087 64820 21960 1215 57325 33428 78453 58786 17945 69270 39787 5877 89224 68993 52157 45418 6371 55883 24247 60621 30674 7411 2636 32373 88270 57333 87458 21264 92112 93018 85581
stdout
copy 
883338598
https://ideone.com/z6etlu
language:
C++14 (gcc 8.3)
created:
7 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!