首页 > 其他分享 >CF924D Contact ATC

CF924D Contact ATC

时间:2024-08-22 13:15:56浏览次数:7  
标签:typedef ATC ll long pair Contact CF924D operatorname define

思路:

考虑函数 \(\operatorname{F}(v_0)_i\) 表示风速为 \(v_0\) 时,\(i\) 到达原点的时间,易得:

\[\operatorname{F}(v_0)_i = \frac{x_i}{v_i+v_0} \]

则若 \((i,j)\) 满足条件,需要满足 \(\operatorname{F}(v_0)_i\) 与 \(\operatorname{F}(v_0)_j\) 的交点的横坐标在 \([-m,m]\) 间,那么若 \(\operatorname{F}(v_0)_i=\operatorname{F}(v_0)_j\),即 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\)。

根据零点存在定理:若区间 \([l,r]\) 满足 \(\operatorname{f}(l) \le 0\) 且 \(\operatorname{f}(r) \ge 0\),且函数连续,则 \([l,r]\) 至少有一个 \(\operatorname{f}(x)\) 的零点。

那么判定 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\) 在 \([-w,w]\) 是否有零点,只需要满足 \(\operatorname{F}(-w)_i-\operatorname{F}(-w)_j \le 0\) 且 \(\operatorname{F}(w)_i-\operatorname{F}(w)_j \ge 0\)

注意到 \(\operatorname{F}(x)_i\) 有单调性,则设 \(l_i=\operatorname{F}(-w)_i,r_i=\operatorname{F}(w)_i\)。

则需要满足 \(l_i \le l_j<0\) 即 \(l_i \le l_j\),且 \(r_i-r_j \ge 0\) 即 \(r_i \ge r_j\)。

那么若 \([l_i,r_i]\) 将 \([l_j,r_j]\) 包含,则 \((i,j)\) 是有贡献的,这个问题是简单题,不作多说,直接树状数组维护即可。

时间复杂度为 \(O(N \log N)\)。

注意离散化。

完整代码:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double ld;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e6+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
    ll l,r;
	bool operator<(const Node&rhs)const{
		if(r!=rhs.r)
		  return r<rhs.r;
		return l>rhs.l;
	}
}A[N];
ll T,n,m,l1,l2,ans;
ld L[N],R[N],h1[N],h2[N];
ll x[N],v[N],a[N];
void add(ll x){
	for(int i=x;i<=l1;i+=lowbit(i))
	  a[i]++;
}
ll query(ll x){
	ll ans=0;
	for(int i=x;i;i-=lowbit(i))
	  ans+=a[i];
	return ans;
}
void work(ld &x){
	x=floor(x*1e11)/1e11;
}
void solve(){
    l1=l2=ans=0;
    n=read(),m=read();
    For(i,1,n){
        x[i]=-read();
        v[i]=read();
        L[i]=(ld)x[i]/((ld)v[i]-m);
        R[i]=(ld)x[i]/((ld)v[i]+m);
        work(L[i]),work(R[i]);
        h1[++l1]=L[i];
        a[l1]=0;
        h2[++l2]=R[i];
    }
    sort(h1+1,h1+l1+1);
    l1=unique(h1+1,h1+l1+1)-(h1+1);
    sort(h2+1,h2+l2+1);
    l2=unique(h2+1,h2+l2+1)-(h2+1);
    For(i,1,n){
        A[i].l=lower_bound(h1+1,h1+l1+1,L[i])-h1;
        A[i].r=lower_bound(h2+1,h2+l2+1,R[i])-h2;
        //cerr<<A[i].l<<' '<<A[i].r<<'\n';
    }
    sort(A+1,A+n+1);
	for(int i=1;i<=n;i++){
		ans+=i-1-query(A[i].l-1);
		add(A[i].l);
	}
    write(ans);
    putchar('\n');
}
bool End;
int main(){
    //open("wind.in","wind.out");
    T=1;
    while(T--)
      solve();
	return 0;
}

标签:typedef,ATC,ll,long,pair,Contact,CF924D,operatorname,define
From: https://www.cnblogs.com/rgw2010/p/18373297

相关文章

  • mybatis-plus配置自定义sqlInjector(使用InsertBatchSomeColumn),出现Invalid bound stat
    项目一开始未引入mybatis-plus,使用的是mybatis,配置文件为xml,有一个配置类中配置了SqlSessionFactory的相关内容。引入mybatis-plus后,想使用InsertBatchSomeColumn遇到Invalidboundstatement(notfound),多处配置发现没有效果并依旧报错,最终在刚才的配置类中的SqlSessionFact......
  • CF/ATc随机乱做
    马上也快退役了,干点自己想干的事吧,别太功利了。早就想开这个记录了,碍于之前学校各种各样的题单让我没时间做(其实时间是颓没的)。现在感觉做啥都也无所谓了,开始记录吧!本博客就简单记录一下,就记个大体思路。1.CF1773GGameofQuestions*2800很神的状压DP啊,发现人数不多遂想到......
  • 再见了Try-Catch,ECMA增加安全赋值运算符提案
    JavaScript的错误处理即将获得重大升级。新的ECMAScript安全赋值运算符提案(?=)旨在通过减少对传统try-catch代码块的需求,来简化您的代码。让我们一起来看看这个提案如何简化您的错误管理,并使您的JavaScript代码更干净、更高效。简单示例传统的try-catch代码块常常导致代......
  • AtCoder Beginner Contest 046
    A-AtCoDeerandPaintCans#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); set<int>s; for(inti=0;i<3;i++){ intx; cin>>x; s.inser......
  • 第47课 Scratch入门篇:水果忍者
    水果忍者故事背景: 水果忍者是一款传统的非常好玩的游戏,我们通过鼠标控制水果刀,把弹出的水果切掉,如果切到地雷则扣分,这款游戏非常好玩,现在我们现在通过Scratch把它做出来,!程序原理: 这款游戏难点就是水果的抛起和下降,由于角色是从下往上走,也就是Y坐标慢慢变大。我......
  • vue3 响应式 API:watch()、watchEffect()
    watch()基本概念watch()用于监视响应式数据的变化,并在数据变化时执行相应的回调函数。可以监视单个响应式数据、多个响应式数据的组合,或者一个计算属性。返回值返回一个函数,调用这个函数可以停止监视。特点watch()默认是懒侦听的,即仅在侦听源发生变化时才执行回调函......
  • [AtCoder - tdpc_game] :ゲーム 题解
    [AtCoder-tdpc_game]:ゲーム题解一道小清新\(dp\)题。定义\(dp_{i,j}\)为第一堆山还有\(i\)个物品,第二堆山还有\(j\)个物品,すぬけ君能取得物品的最大价值。由于只能取两座山最上面的物品,假设当前两座山分别有\({x,y}\)个物品,すぬけ君选后只能有两种情况,分别为\(d......
  • AtCoder ABC 367
    前言本题解部分思路来自于网络,仅供参考。A-ShoutEveryday题目大意给定Takahashi每天的睡觉时间和起床时间,求Takahashi在$A$时是睡着的还是清醒的。解题思路根据题意模拟即可。code#include<bits/stdc++.h>usingnamespacestd;intmain(){inta,b,c;......
  • 释放创意潜能:Scratch跨格式导出全攻略
    标题:释放创意潜能:Scratch跨格式导出全攻略Scratch,这款专为儿童和创意编程爱好者设计的编程工具,以其易用性和趣味性,在全球范围内受到广泛欢迎。但你知道吗?除了在Scratch平台上分享和运行作品,Scratch还支持将项目导出为多种格式,让创意作品在更广阔的舞台上绽放光彩。一、Scr......
  • libtool版本错配(libtool version mismatch)
    当使用configure和makefile编译项目时,出现如下报错:libtool:Versionmismatcherror.Thisislibtool2.4.6,butthe``libtool:definitionofthisLT_INITcomesfromlibtool2.4.7.libtool:Youshouldrecreateaclocal.m4withmacrosfromlibtool2.4.6libtool:an......