记录编号	425805	评测结果	AAAAAAAAAA
题目名称	凯伦和咖啡	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.589 s
提交时间	2017-07-15 20:54:18	内存使用	6.62 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=200000+10;
const int qrt=450;
int n,k,m,bl,blm,mx,an,mn=0x7fffffff;
int block[M],f[qrt],adda[qrt],len[qrt],val[M],beg[qrt],bend[qrt],zuo[M],you[M],ans[M];
bool pdnum[M],pdbl[qrt];
struct DATE{
	int l,r,bh;
}date[M];
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<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline bool cmp(DATE x,DATE y){
	if(block[x.l]==block[y.l]) return x.r<y.r;
	return block[x.l]<block[y.l];
}
inline void add(int l,int r){
	int le=block[l],ri=block[r];
	if(le==ri){
		if(pdbl[le]) return ;
		for(int i=l;i<=r;i++){
			if(pdnum[i]) continue;
			val[i]++;
			if(val[i]+adda[le]>=k){
				f[le]++;pdnum[i]=1;
				if(f[le]==len[le]){
					pdbl[le]=1;
					return ;
				}
			}
		}
		return ;
	}
	if(ri-le>1){
		for(int i=le+1;i<=ri-1;i++){
			if(pdbl[i]) continue;
			adda[i]+=1;
			if(adda[i]>=k){
				pdbl[i]=1;
				f[i]=len[i];
			}
		}
	}
	if(!pdbl[le]){
		for(int i=l;i<=bend[le];i++){
			if(pdnum[i]) continue;
			val[i]++;
			if(val[i]+adda[le]>=k){
				f[le]++;pdnum[i]=1;
				if(f[le]==len[le]){
					pdbl[le]=1;
					break;
				}
			}
		}
	}
	if(!pdbl[ri]){
		for(int i=beg[ri];i<=r;i++){
			if(pdnum[i]) continue;
			val[i]++;
			if(val[i]+adda[ri]>=k){
				f[ri]++;pdnum[i]=1;
				if(f[ri]==len[ri]){
					pdbl[ri]=1;
					break;
				}
			}
		}
	}
} 
inline void init(){
	for(int i=blm;i<=bl;i++){
		if(pdbl[i]) continue;
		for(int j=beg[i];j<=bend[i];j++){
			if(pdnum[j]||val[j]+adda[i]<k) continue;
			pdnum[j]=1;f[i]+=1;
			if(f[i]==len[i]) pdbl[i]=1;
		}
	}
}
inline int query(int pos,int zhi){
	int blo=block[pos];
	if(pdbl[blo]||pdnum[pos]) an+=zhi;
}
int DK(){
	freopen("coffee.in","r",stdin);
	freopen("coffee.out","w",stdout);
	int aa,bb;
	n=read();k=read();m=read();
	for(int i=1;i<=n;i++){
		zuo[i]=read();you[i]=read();
		mn=min(mn,zuo[i]);mx=max(mx,you[i]);
	}
	for(int i=mn;i<=mx;i++) block[i]=(i-1)/qrt+1;
	bl=block[mx];blm=block[mn];
	for(int i=blm;i<bl;i++){
		beg[i]=(i-1)*qrt+1;
		bend[i]=i*qrt;
		len[i]=qrt;
	}
	beg[bl]=bend[bl-1]+1;beg[blm]=mn;
	bend[bl]=mx;
	len[bl]=bend[bl]-beg[bl]+1;
	len[blm]=bend[blm]-beg[blm]+1;
	for(int i=1;i<=n;i++) add(zuo[i],you[i]);
	init();
	for(int i=1;i<=m;i++){
		aa=read();bb=read();
		date[i].bh=i;
		date[i].l=max(mn,aa);date[i].r=min(mx,bb);
	}
	sort(date+1,date+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		if(date[i].l>date[i].r){
			ans[date[i].bh]=0;continue;
		}
		for(;r<date[i].r;r++) query(r+1,1);
		for(;r>date[i].r;r--) query(r,-1);
		for(;l<date[i].l;l++) query(l,-1);
		for(;l>date[i].l;l--) query(l-1,1);
		ans[date[i].bh]=an;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0; 
}
int dk=DK();
int main(){
	;
}