# Untitled

unknown
c_cpp
a year ago
1.6 kB
6
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
#define int long long int
int x[1000001]={0};
void solve(){
int N, K, Q;
cin>>N>>K>>Q;

int l[N], r[N];
for(int i=0; i<N; i++){
cin>>l[i]>>r[i];
// cout<<l[i]<<" "<<r[i]<<"\n";
// for(int j=l[i]; j<=r[i]; j++){
//     x[j]++;
// }    galat hai complexity jaada ho jayega
x[l[i]]++;
x[r[i]+1]--;
// hamko l[i] se r[i] sab +1 karna hai toh l[i] pe ++ daal denge phir r+1 pe --
// isse phir jab prefix sum lenge toh r ke baad wale ++ -- se cancel ho jayega
// aisa soch sakte ho

}
for(int i=1;i<=1000000;i++){
x[i]=x[i]+x[i-1];
}
int L[Q], R[Q];
for(int i=0; i<Q; i++){
cin>>L[i]>>R[i];
// cout<<L[i]<<" "<<R[i]<<"\n";
}
// jo bhi index pe value >=k hai usko as a +1 kar sakte hai phir prefix sum lelenge toh range ka directly nikal sakte hai

// basically dekh rha ki koan koan se index pe value >=k hai
for(int i=0;i<=10;i++){
if(x[i]>=K){x[i]=1;}
else{x[i]=0;}
}
// phir se prefix technique lgana padega
for(int i=1;i<=1000000;i++){
x[i]=x[i]+x[i-1];
}

for(int i=0; i<Q; i++){
// int sum=0;
// for(int j=L[i]; j<=R[i]; j++){
//     if(x[j]>=3) // ye kyu >k bola hai na ques main toh >=3
//         sum++;
// }
int sum=x[R[i]]-x[L[i]-1];  // aise direct nikal lenge
cout<<sum<<'\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
while(t--){
solve();
}
}```