COGS——T 2739. 凯伦和咖啡
2024-08-23 02:16:02
http://www.cogs.pro/cogs/problem/problem.php?pid=2739
★★☆ 输入文件:coffee.in
输出文件:coffee.out
简单对比
时间限制:1 s 内存限制:512 MB
【题目描述】
为了在上课时保持清醒,凯伦需要一些咖啡。咖啡爱好者凯伦想知道最佳的温度来冲煮完美的咖啡。因此,她花了一些时间阅读几本食谱,其中包括广受好评的“咖啡的艺术”。
她知道有n个食谱,其中第i个食谱建议应当在li和ri度之间冲煮以达到最佳的味道。凯伦认为如果至少k个食谱推荐某个温度,那么那个温度是可以接受的。
凯伦的性格比较多变,因此她会问q个问题,对于每一个问题,她会给出一个温度区间[a,b],你要告诉她有多少可接受的整数温度在这个范围内。
【输入格式】
第一行输入包含三个整数,n,k(1≤k≤n≤200000)和q(1≤q≤200000),如题中所描述。
接下来n行描述每一个食谱,具体来说,其中的第i行包含两个整数li和ri(1≤li≤ri≤200000),描述第i个食谱建议咖啡在li和ri度之间进行冲煮(包括端值)。
接下来q行为q个询问。这些行中的每一行都包含a和b,(1≤a≤b≤200000),表示她想知道a和b度之间的可接受的整数温度的数量,包括a和b。
【输出格式】
对于每个询问,一行输出一个答案。
【样例输入】
3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100
【样例输出】
3
3
0
4
【提示】
数据进行了更新,卡掉了部分暴力程序。
【来源】
线段树//分块//(好像有线性作法呃呃呃)
#include <cstdio> const int N(+);
int n,q,k;
struct Tree
{
int l,r,sum,flag,ret;
}tr[N<<];
#define lc (now<<1)
#define rc (now<<1|1)
#define mid (tr[now].l+tr[now].r>>1)
void Tree_build(int now,int l,int r)
{
tr[now].l=l,tr[now].r=r;
if(l==r)
{
tr[now].flag=;
tr[now].sum=;
return ;
}
Tree_build(lc,l,mid);
Tree_build(rc,mid+,r);
}
void Tree_add(int now,int l,int r)
{
if(tr[now].l>=l&&tr[now].r<=r)
{
tr[now].sum++;
return ;
}
if(r<=mid) Tree_add(lc,l,r);
else if(l>mid) Tree_add(rc,l,r);
else Tree_add(lc,l,mid),Tree_add(rc,mid+,r);
}
int Tree_query(int now,int l,int r)
{
if(tr[now].l==l&&tr[now].r==r) return tr[now].sum;
if(r<=mid) return Tree_query(lc,l,r);
else if(l>mid) return Tree_query(rc,l,r);
else return Tree_query(lc,l,mid)+Tree_query(rc,mid+,r);
}
void Tree_push(int now)
{
if(tr[now].flag)
{
if(tr[now].sum>=k) tr[now].sum=;
else tr[now].sum=;
return ;
}
tr[lc].sum+=tr[now].sum;
tr[rc].sum+=tr[now].sum;
tr[now].sum=;
Tree_push(lc); Tree_push(rc);
tr[now].sum=tr[lc].sum+tr[rc].sum;
} inline void read(int &x)
{
x=; register char ch=getchar();
for(;ch>''||ch<'';) ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
} #define swap(a,b) {int tmp=a;a=b;b=tmp;}
int AC()
{
freopen("coffee.in","r",stdin);
freopen("coffee.out","w",stdout);
read(n),read(k),read(q);
Tree_build(,,N);
for(int l,r;n--;)
{
read(l),read(r);
if(l>r) swap(l,r);
Tree_add(,l,r);
}
Tree_push();
for(int l,r;q--;)
{
read(l),read(r);
if(l>r) swap(l,r);
printf("%d\n",Tree_query(,l,r));
}
return ;
} int Hope=AC();
int main(){;}
最新文章
- 7.让网站支持http和https的访问方式
- 详细学习ORACLE JOBS
- jboss使用(eap 6.0以后版本)
- 关于fastclick.js
- Stack的三种含义(数据超过栈的大小,就发生stack overflow)
- 今天工作中遇到的根据用户id取得产品大类和相关小类的问题
- C# 7 函数 青歌赛打分 天气预报
- js处理json的方法
- 测试驱动 ASP.NET MVC 和构建可测试 ASP.NET MVC 应用程序
- 使用Excel背单词-高效-简单
- 最简单的epoll的使用范例 : 监听 标准输入 ,并将数据回显到终端
- OFFICE 文档转换为html在线预览
- 容器_JDK源码分析_自己简单实现ArrayList容器
- jquery无new构建学习笔记
- 网站https证书SSL证书相关
- 【Codeforces Round 1132】Educational Round 61
- Python-元组-10
- Swift学习笔记6
- Oracle EBS AR 收款取数
- weblogic创建域生产模式,输入用户名闪退