首页 > 代码库 > #419(div2) B. Karen and Coffee

#419(div2) B. Karen and Coffee

题意:给出n个温度区间,k,Q个询问,每个询问给出一个温度区间x--y。问这之间有多少个温度在给出K的温度区间内。

思路:前缀和小技巧

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 3e5+10;
 4 
 5 int n,k,q,x,y,a[N],b[N];
 6 
 7 int main() {
 8     scanf("%d%d%d",&n,&k,&q);
 9     for(int i = 1; i <= n; ++i) {
10         scanf("%d%d",&x,&y);
11         b[x] += 1;
12         b[y+1] += -1;
13     }
14     for(int i = 1; i <= 200000; ++i) {
15         b[i] += b[i-1];
16         if(b[i] >= k) {
17             a[i] = 1;
18         }
19         else {
20             a[i] = 0;
21         }
22     }
23     for(int i = 1; i <= 200000; ++i) a[i] += a[i-1];
24     for(int i=1;i<=q;i++) {
25         int x,y;
26         scanf("%d%d",&x,&y);
27         cout<<a[y] - a[x-1]<<endl;
28     }
29     return 0;
30 }

 

#419(div2) B. Karen and Coffee