AtCoder Regular Contest 084 C - Snuke Festival【二分】
2024-10-08 03:02:59
....最后想到了,可是不应该枚举a[],这样要二重循环,而应该枚举b[],这样只需一重循环。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
int a[maxn],b[maxn],c[maxn];
int n; int FindLastSmaller(int key)
{
int l=,r=n-;
while(l<=r){
int mid=(l+r)>>;
if(a[mid]>=key) r=mid-;
else l=mid+;
}
return r;
} int FindFirstLarger(int key)
{
int l=,r=n-;
while(l<=r){
int mid=(l+r)>>;
if(c[mid]>key) r=mid-;
else l=mid+;
}
return l;
} int main()
{
cin>>n;
for(int i=;i<n;i++) cin>>a[i];
for(int i=;i<n;i++) cin>>b[i];
for(int i=;i<n;i++) cin>>c[i];
sort(a,a+n);
sort(b,b+n);
sort(c,c+n);
ll ans=;
for(int i=;i<n;i++){
ll p1=FindLastSmaller(b[i]);
ll p2=FindFirstLarger(b[i]);
ans+=(p1+)*(n-p2);
}
cout<<ans<<endl;
return ;
}
lower_bound(),upper_bounder()不能再好用。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
int a[maxn], b[maxn], c[maxn];
int n; int main()
{
scanf("%d", &n);
for (int i = ; i < n; i++) scanf("%d", &a[i]);
for (int i = ; i < n; i++) scanf("%d", &b[i]);
for (int i = ; i < n; i++) scanf("%d", &c[i]);
sort(a, a + n);
sort(b, b + n);
sort(c, c + n);
ll ans = ;
for (int i = ; i<n; i++) {
ll p = lower_bound(a, a + n, b[i]) - a;
ll q = upper_bound(c, c + n, b[i]) - c;
ans += p*(n - q);
}
printf("%lld\n", ans);
}
最新文章
- java编码解码乱码问题
- offer
- 使用 CSS3 制作一组超时尚的动画按钮效果
- 通过布赛尔曲线以及CAShapeLayer的strokeStart 、strokeEnd 属性来实现一个圆形进度条
- c++ 弧度值与角度值的转换
- Swift数据类型之整型和浮点型-备
- Python快捷键
- linux反弹shell
- MATLAB 2012b license checkout failed
- nuxt.js实战之用vue-i18n实现多语言
- Winform-DataGridView
- python基础之 编码进阶,文件操作和深浅copy
- 随机漂浮图片、右侧上下浮动快捷栏JS
- node-inspector调试工具
- Nuke的色彩匹配节点思路
- hadoop报错:hdfs.DFSClient: Exception in createBlockOutputStream
- MariaDB 主从同步与热备(14)
- Java 8 日期时间API
- Adaptive Thresholding &; Otsu’s Binarization
- jquery判断元素的子元素是否存在