记录编号 |
444073 |
评测结果 |
AAAAAAAAAA |
题目名称 |
凯伦和咖啡 |
最终得分 |
100 |
用户昵称 |
Lovelove_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;
}