fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. ll T[400055]={0},U[400055]={0},A[100020]={0};
  7. void build(ll node,ll s,ll e){
  8. 	if(s==e)
  9. 		T[node]=0;
  10. 	else{
  11. 		ll mid=(s+e)>>1;
  12. 		build(2*node,s,mid);
  13. 		build(2*node+1,mid+1,e);
  14. 	}
  15. }
  16. void update(ll node,ll s,ll e,ll x,ll y,ll val){
  17. 	if(U[node]!=0){
  18. 		T[node]+=(e-s+1)*U[node];
  19. 		if(s!=e){
  20. 			U[2*node]+=U[node];
  21. 			U[2*node+1]+=U[node];
  22. 		}
  23. 		U[node]=0;
  24. 	}
  25.  
  26. 	if(s>e || s>y || e<x)
  27. 		return;
  28. 	if(s>=x && e<=y){
  29. 		T[node]+=(e-s+1)*val;
  30. 		if(s!=e){
  31. 			U[2*node]+=val;
  32. 			U[2*node+1]+=val;
  33. 		}
  34. 		return ;
  35. 	}
  36. 	ll mid=(s+e)>>1;
  37. 	update(2*node,s,mid,x,y,val);
  38. 	update(2*node+1,mid+1,e,x,y,val);
  39. 	T[node]=T[2*node]+T[2*node+1];
  40. }
  41.  
  42.  
  43. ll find(ll node,ll s,ll e,ll x,ll y){
  44. 	if(x>e || y<s)
  45. 		return 0;
  46. 	if(U[node]!=0){
  47. 		T[node]+=(e-s+1)*U[node];
  48. 		if(s!=e){
  49. 			U[2*node]+=U[node];
  50. 			U[2*node+1]+=U[node];
  51. 		}
  52. 		U[node]=0;
  53. 	}
  54. 	if(s>=x && e<=y){
  55. 	    ll x=T[node];
  56. 	    T[node]=U[node]=0;
  57. 	    return x;
  58. 	}
  59. 	ll mid=(s+e)>>1;
  60. 	ll p1=find(2*node,s,mid,x,y);
  61. 	ll p2=find(2*node+1,mid+1,e,x,y);
  62. 	T[node]=0;
  63. 	return p1+p2;
  64. }
  65.  
  66. int main(){
  67. 	ll t;
  68. 	cin>>t;
  69. 	while(t--){
  70. 		ll n,k,a,b;
  71. 		cin>>n>>k;
  72. 		ll c=INT_MIN;
  73. 		ll R[n+1],L[n+1];
  74. /*
  75. 		memset(A,0,sizeof(A));
  76. 		memset(T,0,sizeof(T));
  77. 		memset(U,0,sizeof(U));*/
  78. 		vector<ll> B,C;
  79.  
  80. 		for(ll i=0;i<n;i++){
  81. 			cin>>L[i]>>R[i];
  82. 	        c=max(c,R[i]+3);
  83. 		}
  84. 	//	build(1,1,c);
  85. 		for(ll i=0;i<n;i++){
  86. 			update(1,1,c,L[i],R[i],1);
  87. 		}
  88.  
  89. 		for(ll i=1;i<c;i++){
  90. 			A[i]=find(1,1,c,i,i);
  91. 			if(A[i]==k+1)
  92. 				B.push_back(i);
  93.  
  94. 			if(A[i]==k)
  95. 				C.push_back(i);
  96. //A[i]=0;
  97. 		}
  98.  
  99. 		ll ans=INT_MIN;
  100. 		ll x,y;
  101. 		for(ll i=0;i<n;i++){
  102. 			x=lower_bound(B.begin(),B.end(),L[i])-B.begin();
  103. 			y=lower_bound(B.begin(),B.end(),R[i])-B.begin();;
  104. 			if(y==B.size() || B[y]!=R[i])
  105. 				y--;
  106. 			a=y-x+1;
  107. 			x=lower_bound(C.begin(),C.end(),L[i])-C.begin();;
  108. 			y=lower_bound(C.begin(),C.end(),R[i])-C.begin();;
  109. 			if(y==C.size() ||C[y]!=R[i])
  110. 				y--;
  111. 			a+=C.size();
  112. 			a-=y-x+1;
  113. 			ans=max(ans,a);
  114. 		}
  115.  
  116. 	/*	for(ll i=0;i<4*c;i++){
  117. 		    U[i]=T[i]=0;
  118. 		}
  119. 	*//*	for(ll i=1;i<c;i++) 
  120. 			cout<<A[i]<<" "<<i<<endl;
  121. */
  122. 		cout<<ans<<endl;
  123. 	}	
  124. }
  125.  
  126.  
Success #stdin #stdout 0s 22272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/QUz7HY
language:
C++14 (gcc 8.3)
created:
6 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!