记录编号	434041	评测结果	AAAAAAAAAA
题目名称	凯伦和咖啡	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.656 s
提交时间	2017-08-06 21:26:20	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 200010
int n,k,q;
int len,match[N],cun[N];
int pre[N],ma;
inline int read(){
  int x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){
    if(ch=='-')
      f=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9'){
    x=(x<<1)+(x<<3)+ch-'0';
    ch=getchar();
  }
  return x*f;
}
inline int query(int x,int y){
	int ans=0;
	if(match[x]+1>match[y])
		pos(i,x,y)
			ans+=pre[i]>=k?1:0;
	else{
		for(int i=x;i;i++){
			if(match[i]!=match[x])
				break;
			ans+=pre[i]>=k?1:0;
		}
		for(int i=y;i;i--){
			if(match[i]!=match[y])
				break;
			ans+=pre[i]>=k?1:0;
		}
		pos(i,match[x]+1,match[y]-1)
			ans+=cun[i];
	}
	return ans;
}
inline int haha(){
	freopen("coffee.in","r",stdin);
	freopen("coffee.out","w",stdout);
	n=read();k=read();q=read();
	pos(i,1,n){
		int l,r;
		l=read();r=read();
		pre[l]++;pre[r+1]--;
		ma=max(ma,r);
	}
	len=(int)sqrt(ma+0.5);
	pos(i,1,ma)
		match[i]=(i-1)/len+1;
	pos(i,1,ma){
		pre[i]+=pre[i-1];
	}
	pos(i,1,match[ma]){
		pos(j,1,ma)
			if(match[j]==i)
				cun[i]+=pre[j]>=k?1:0;
	}
	pos(i,1,q){
		int l=read(),r=read();
		printf("%d\n",query(l,r));
	}
	return 0;
}
int sb=haha();
int main(){
	;
}