链接:https://ac.nowcoder.com/acm/contest/16/A
来源:牛客网

题目描述

FST是一名可怜的小朋友,他很强,但是经常fst,所以rating一直低迷。
但是重点在于,他非常适合ACM!并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本,但是FST发现,在价格能承受的范围内,笔记本的内存和速度是不可兼得的。
可是,有一些笔记本是被另外一些“完虐”的,也就是内存和速度都不高于另外某一个笔记本,现在FST想统计一下有多少笔记本被“完虐”。

输入描述:

第一行一个正整数n,
表示笔记本的数量。接下来n行,每行两个正整数M

i

,S

i

表示这款笔记本的内存和速度。
n≤10

5

,M

i

,S

i

≤10

9

输出描述:

一行,一个正整数,表示被完虐的笔记本数。
示例1

输入

复制

4
100 700
200 500
50 100
300 400

输出

复制

1

备注:

M

i

和S

i

都是越大越优。
数据保证M

i

互不相同,S

i

也互不相同。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<cmath> const int maxn=2e5+;
typedef long long ll;
using namespace std; struct node
{
int l,r;
int num;
}tree[maxn<<];
struct node1
{
int a,b;
bool friend operator <(node1 x,node1 y)
{
return x.a>y.a;
}
}p[maxn];
vector<int>v;
void build(int m,int l,int r)
{
tree[m].l=l;
tree[m].r=r;
tree[m].num=;
if(l==r)
{
return ;
}
int mid=(l+r)>>;
build(m<<,l,mid);
build(m<<|,mid+,r);
}
void update(int m,int pos,int val)
{
if(tree[m].l==tree[m].r&&tree[m].l==pos)
{
tree[m].num=val;
return ;
}
int mid=(tree[m].l+tree[m].r)>>;
if(pos<=mid)
update(m<<,pos,val);
else
{
update(m<<|,pos,val);
}
tree[m].num=(tree[m<<].num+tree[m<<|].num);
}
int query(int m,int l,int r)
{
if(tree[m].l==l&&tree[m].r==r)
{
return tree[m].num;
}
int mid=(tree[m].l+tree[m].r)>>;
if(r<=mid)
{
return query(m<<,l,r);
}
else if(l>mid)
{
return query(m<<|,l,r);
}
else
{
return query(m<<,l,mid)+query(m<<|,mid+,r);
}
}
int getid(int x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+;
}
int main()
{
int n;
cin>>n;
for(int t=;t<n;t++)
{
scanf("%d%d",&p[t].a,&p[t].b);
v.push_back(p[t].a);
v.push_back(p[t].b);
//p[t].pos=t;
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
sort(p,p+n);
build(,,*n);
ll ans=;
for(int t=;t<n;t++)
{
update(,getid(p[t-].b),); if(query(,getid(p[t].b),*n))
{
// cout<<query(1,1,getid(p[t].b)-1)<<endl;
ans++;
}
}
printf("%lld\n",ans);
return ;
}

最新文章

  1. Windows Azure Virtual Machine (27) 使用psping工具,测试Azure VM网络连通性
  2. JS区别不同浏览器(微信、手机等)
  3. Asp.net MVC 批量删除数据
  4. DBCP连接Oracle,数据库重启后现OALL8 is in an inconsistent state异常
  5. php 递归 适合刚刚接解递归的人看
  6. POJ 2826 An Easy Problem?!
  7. onitemcommand 的作用以及onitemdatabound的具体作用
  8. 【HDOJ】1601 Galactic Import
  9. 一个在浏览器端将html 转为pdf 的js 插件 jsPDF
  10. PAT (Advanced Level) 1003. Emergency (25)
  11. mvc/mvvm小小的总结
  12. STM32W108无线射频模块通用IO接口应用实例
  13. iOS-键盘监听YYKeyboardManager
  14. 50行代码实现的一个最简单的基于 DirectShow 的视频播放器
  15. WMI Explorer操作 和 powershell命令
  16. sqlserver 脚本生成数据库文档
  17. 牛客练习赛 43 B-Tachibana Kanade Loves Probability
  18. CCF-炉石传说
  19. Anchor 的两种编程实现
  20. python SMTP

热门文章

  1. dos下mybatis自动生成代码
  2. 关于Exceptionless日志收集框架如何关闭磁盘缓存
  3. 039_go语言中的排序
  4. 静态集成腾讯TBS X5内核WebView,从微信提取新版30M浏览器内核打包进apk
  5. Ubuntu用户都应该了解的快捷键
  6. IndexFlatL2、IndexIVFFlat、IndexIVFPQ三种索引方式示例
  7. SqlServer 版本号
  8. ALGEBRA-前言
  9. C#LeetCode刷题-几何
  10. Homekit_二路继电器