「ZJOI2019」浙江省选

在八月来临前补完了zjoi2019

本来是想在八月前做完暑假作业的？

传送门

Description

给\(n\)条斜率为正的直线，询问每条直线是否在某处高度为前\(m\)名，如果是，询问最小排名

Solution

依次求可以为第\(i\)名的直线

对确定不能为前\(i-1\)名的直线，求一次第一象限内的半平面交，要求每个线段都能覆盖至少一个整数

对可以为前\(i-1\)名的直线二分求出覆盖的区间

通过扫描得到凸壳上可以为第\(i\)名的线段

点的横坐标可能很大，维护一个分数类，支持floor()和ceil()

复杂度\(O(mn\log n)\)

Code

#include<bits/stdc++.h>

#define ll long long

using namespace std;

#define reg register

#define P(x) a[p[x]]

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

const int MN=1e5+5;

const ll inf=1e18;

int n,m,ans[MN];

struct line{

	ll b;int k,id;

	void Read(int i){k=read();b=read();id=i;}

	bool operator<(const line&o)const{return k<o.k||(k==o.k&&b>o.b);}

}a[MN];int top,p[MN];

struct Frac{

    ll a,b,c;//c+(a/b)

	Frac(ll x,ll y){if(y<0)x=-x,y=-y;c=x/y,b=y,a=x%y;if(a<0)--c,a+=b;}

    bool operator <(const Frac&o)const{return c^o.c?c<o.c:a*o.b<b*o.a;}

    bool operator ==(const Frac&o)const{return c==o.c&&a*o.b==b*o.a;}

    bool operator <=(const Frac&o)const{return *this<o||*this==o;}

    ll floor(){return c;}

    ll ceil(){return c+(a>0);}

};

Frac _(line x,line y){return Frac(y.b-x.b,x.k-y.k);}

void Calc()

{

	top=0;reg int i;

	for(i=1;i<=n;++i)if(!~ans[a[i].id])

	{

		if(top&&P(top).k==a[i].k) continue;

		while(top>1&&_(a[i],P(top)).floor()<_(P(top),P(top-1)).ceil()) --top;

		if(top==1&&a[i].b>P(1).b) --top;

		p[++top]=i;

	}

	a[0].b=P(1).b;

}

pair<ll,int> key[MN<<1];int ktp;

void call(int i)

{

	int l=1,r=top,mid,pos=0;

	for(;l<=r;)

	{

		mid=(l+r)>>1;

		if(P(mid).k>=a[i].k||mid==top?1:_(P(mid),a[i])<=_(P(mid),P(mid+1))) pos=mid,r=mid-1;

		else l=mid+1;

	}

	key[++ktp]=make_pair(P(pos).k>=a[i].k?0:_(P(pos),a[i]).floor()+1,1);

}

void calr(int i)

{

	if(a[i].k>P(top).k) return;

	int l=1,r=top,mid,pos=0;

	for(;l<=r;)

	{

		mid=(l+r)>>1;

		if(P(mid).k<=a[i].k||_(P(mid-1),P(mid))<=_(P(mid),a[i])) pos=mid,l=mid+1;

		else r=mid-1;

	}

	if(P(pos).k>a[i].k)key[++ktp]=make_pair(_(P(pos),a[i]).ceil(),-1);

}

void GetKey()

{

	reg int i;

	for(ktp=0,i=1;i<=n;++i)if(~ans[a[i].id]){call(i);calr(i);}

	std::sort(key+1,key+ktp+1);

}

int main()

{

	n=read(),m=read();

	reg int i,j,k,o;

	for(i=1;i<=n;++i) a[i].Read(i),ans[i]=-1;

	std::sort(a+1,a+n+1);

	for(o=1;o<=m;++o)

	{

		Calc();GetKey();

  		for(i=j=1,k=0;i<=top;++i)

		{

    		ll l=_(P(i),P(i-1)).ceil(),r=i==top?inf:_(P(i),P(i+1)).floor();

    		while(j<=ktp&&key[j].first<=l)k+=key[j++].second;

    		if(k==o-1) ans[P(i).id]=o;

    		while(j<=ktp&&key[j].first<=r)

			{

      			reg int jj=j;

      			while(jj<=ktp&&key[jj].first==key[j].first) k+=key[jj++].second;

      			if(k==o-1) ans[P(i).id]=o;

      			j=jj;

    		}

		}

	}

	for(i=1;i<=n;++i) printf("%d ",ans[i]);

	return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

「ZJOI2019」浙江省选

传送门

Description

Solution

Code

最新文章

热门文章