【codeforces 816B】Karen and Coffee
2024-08-31 12:38:38
【题目链接】:http://codeforces.com/contest/816/problem/B
【题意】
给你很多个区间[l,r];
1<=l<=r<=2e5
一个数字如果被k个以上的区间覆盖到;
则称之为特殊数字;
给你q个询问区间;
问你这q个区间里面
每个区间里面有多少个特殊数字;
【题解】
对于覆盖的区间l,r
add[l]++,sub[r+1]++,
然后顺序枚举
now+=add[i];
now-=sub[i];
如果now>=k则i是一个特殊数字;
写个前缀和O(1)输出答案.
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e5+100;
int add[N],sub[N],n,k,q;
int is[N],sum[N];
int main(){
//Open();
Close();
cin >> n >> k >> q;
rep1(i,1,n){
int x,y;
cin >> x >> y;
add[x]++,sub[y+1]++;
}
int now = 0;
rep1(i,1,(int) 2e5){
now+=add[i];
now-=sub[i];
if (now>=k){
is[i] = 1;
}
}
sum[0] = 0;
rep1(i,1,(int) 2e5){
sum[i] = sum[i-1] + is[i];
}
rep1(i,1,q){
int x,y;
cin >> x >> y;
cout << sum[y]-sum[x-1] << endl;
}
return 0;
}
最新文章
- ALSA 学习小记
- Android 数据存储之 SQLite数据库存储
- Java程序员从笨鸟到菜鸟之(十三)java网络通信编程
- Java调用脚本
- 欢迎进入Node.js世界
- PLSQL Developer连接远程Oracle方法(非安装客户端)
- C++ 数据类型及相关问题 及输出精度控制
- install Active Directory域控制器
- 手动更改WIN远程桌面端口,要改两个地方的注册表哟
- OSTaskCreateExt() 建立任务
- Swift - 浮点数转换成整数(四舍五入与直接截断)
- myeclipse8.5打包jar并引入第三方jar包
- SQL优化(面试题)
- springmvc框架原理分析和简单入门程序
- JS进阶1
- SQL基础试题
- LeetCode 318. Maximum Product of Word Lengths (状态压缩)
- nexus 私服跑一跑流程
- python递归——汉诺塔
- 解决Linux下3T硬盘分区只有2T(2199G)可用
热门文章
- 为什么要清除BSS段
- 小学生都能学会的python(文件操作)
- Hdu 1429 胜利大逃亡(续) (bfs+状态压缩)
- 【codeforces 810A】Straight «A»
- jQuery fadeOut无效
- QT5 OpenGL (六, 键盘事件, 开关灯,放大缩小综合运用)
- LeetCode211:Add and Search Word - Data structure design
- google 搜索不跳中间页
- HDU 1040.As Easy As A+B【排序】【如题(水!水!水!)】【8月24】
- Android ImageView 不显示JPEG图片 及 Android Studio中怎样引用图片资源