记录编号 444073 评测结果 AAAAAAAAAA
题目名称 凯伦和咖啡 最终得分 100
用户昵称 GravatarLovelove_boii 是否通过 通过
代码语言 C++ 运行时间 1.954 s
提交时间 2017-09-01 22:01:14 内存使用 2.60 MiB
显示代码纯文本
//Lovelove_boii loves coding
/*暴力大法好
#include<fstream>
using namespace std;
ifstream cin("coffee.in");
ofstream cout("coffee.out");
int n,k,q;
int degree[200001];
int main()
{
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)
	{
		int left_edge,right_edge;
		cin>>left_edge>>right_edge;
		for(int j=left_edge;j<=right_edge;j++)
		{
			degree[j]++;
		}
	}
	for(int i=1;i<=q;i++)
	{
		int ans=0;
		int left_edge,right_edge;
		cin>>left_edge>>right_edge;
		for(int j=left_edge;j<=right_edge;j++)
		{
			if(degree[j]>=k)
			{
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	cin.close();
	cout.close();
	return 0;
}

*/
/*写到一半放弃了的二分
#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("coffee.in");
ofstream cout("coffee.out");
int n,k,q;
class memory
{
public:
	int left_edge,right_edge;
}section[200001];
bool cmp(memory a,memory b)
{
	if(a.left_edge==b.left_edge)
	{
		return a.right_edge<b.right_edge;
	}
	return a.left_edge<b.left_edge;
}
int main()
{
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>section[i].left_edge>>section[i].right_edge;
	}
	sort(section+1,section+n+1,cmp);
	
*/
/*经蛤玮区间覆盖得出的优化解
#include<fstream>
using namespace std;
ifstream cin("coffee.in");
ofstream cout("coffee.out");
int n,k,q;
int section[200001+1],counter[200001];
int main()
{
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)
	{
		int left_edge,right_edge;
		cin>>left_edge>>right_edge;
		section[left_edge]++;
		section[right_edge+1]--;
	}
	int times=0;
	for(int i=1;i<=200000;i++)
	{
		times+=section[i];
		counter[i]=times;
	}
	for(int i=1;i<=q;i++)
	{
		int left_edge,right_edge;
		cin>>left_edge>>right_edge;
		int ans=0;
		for(int j=left_edge;j<=right_edge;j++)
		{
			if(counter[j]>=k)
			{
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	cin.close();
	cout.close();
	return 0;
}

*/
/*最终优化解*/
#include<fstream>
using namespace std;
ifstream cin("coffee.in");
ofstream cout("coffee.out");
int n,k,q;
int section[200001+1],counter[200001],answering[200001];
int main()
{
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)
	{
		int left_edge,right_edge;
		cin>>left_edge>>right_edge;
		section[left_edge]++;
		section[right_edge+1]--;
	}
	int times=0;
	for(int i=1;i<=200000;i++)
	{
		times+=section[i];
		counter[i]=times;
	}
	for(int i=1;i<=200000;i++)
	{
		if(counter[i]>=k)
		{
			answering[i]=answering[i-1]+1;
		}
		else
		{
			answering[i]=answering[i-1];
		}
	}
	for(int i=1;i<=q;i++)
	{
		int left_edge,right_edge;
		cin>>left_edge>>right_edge;
		cout<<answering[right_edge]-answering[left_edge-1]<<endl;
	}
	cin.close();
	cout.close();
	return 0;
}