Luogu P5328 [ZJOI2019] Zhejiang provincial election

Luogu P5328 [ZJOI2019] Zhejiang provincial election

https://www.luogu.com.cn/problem/P5328

Tutorial

https://www.luogu.com.cn/blog/foreverlasting/solution-p5328

Each player can be regarded as a straight line of \ (y=a_ix+b_i\), and his best ranking is to find a non negative integer \ (x\), so that the number of straight lines strictly above it +1 is the smallest

Then, if you want to find all the contestants with rank =1, do a half plane intersection to get those contestants. Note that since \ (x\) can only be non negative integers, you need to consider whether the line has an integral point on the contour. You need to round up and round down, so this question uses fractions to store floating-point numbers

After that, if we delete the straight lines of all the contestants with rank =1, the contestants with rank =2 can also make a half plane intersection, but note that the one with rank =2 is not necessarily on the contour at this time, because for a \ (x\), there may be more than one rank =1 above it

You can calculate the range of \ (x\) above the current contour line for all lines that already have rank at this time, and then you can get the number of lines above the current \ (x\) by difference

Then enumerate each line on the contour line. If there is \ (x\) in its range so that the number of lines above it = current name times -1, its best position is the current position

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
using namespace std;
inline char gc() {
//	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void rd(T &x) {
	x=0; int f=1,ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=gc();}
	x*=f;
}
typedef long long ll;
const ll INF=2e18;
const int maxn=1e5+50;
int n,m,an[maxn];
struct Line {
	int k,id; ll b;
	bool operator <(const Line &other) const {
		if(k!=other.k) return k<other.k;
		return b>other.b;
	}
} L[maxn]; 
struct Frac {
	ll a,b,c;
	Frac() {a=b=0,c=1;}
	Frac(ll x,ll y) {
		if(y<0) x=-x,y=-y;
		a=x/y,b=x%y,c=y;
		if(b<0) b+=y,--a;
	}
	inline bool operator <(const Frac &other) const {
		if(a!=other.a) return a<other.a;
		return b*other.c<other.b*c;
	}
	friend inline bool operator <=(const Frac &a,const Frac &b) {return !(b<a);}
	inline ll fl() {return a;}
	inline ll cl() {return a+bool(b);}
};
inline Frac crosP(Line u,Line v) {
	return Frac(u.b-v.b,v.k-u.k);
}
void sol(int now) {
	static Line q[maxn]; static Frac p[maxn]; int top=0;
	for(int i=1,j=-1;i<=n;++i) if(an[L[i].id]==-1) {
		if(top&&L[i].k==q[top].k) continue;
		while(top&&crosP(q[top],L[i]).fl()<p[top].cl()) --top;
		q[++top]=L[i];
		if(top>1) p[top]=crosP(q[top],q[top-1]);
	}
	p[top+1]=Frac(INF,1);
	vector< pair<ll,int> > tag; 
	for(int i=1;i<=n;++i) if(an[L[i].id]!=-1) {
		{
			int l=1,r=top,re=-1;
			while(l<=r) {
				int mid=(l+r)>>1;
				if(q[mid].k>=L[i].k||crosP(L[i],q[mid])<=p[mid+1]) re=mid,r=mid-1;
				else l=mid+1;
			}
			if(re!=-1&&q[re].k<L[i].k) tag.push_back(make_pair(crosP(L[i],q[re]).fl()+1,1));
			else tag.push_back(make_pair(0,1));
		}
		{
			int l=1,r=top,re=-1;
			while(l<=r) {
				int mid=(l+r)>>1;
				if(q[mid].k<=L[i].k||p[mid]<=crosP(L[i],q[mid])) re=mid,l=mid+1;
				else r=mid-1;
			}
			if(re!=-1&&q[re].k>L[i].k) tag.push_back(make_pair(crosP(L[i],q[re]).cl(),-1));
		}
	}
	sort(tag.begin(),tag.end());
	for(int i=1,k=0,cnt=0;i<=top;++i) {
		while(k<tag.size()&&tag[k].fi<=p[i].cl()) cnt+=tag[k++].se;
		if(cnt==now-1) an[q[i].id]=now;
		while(k<tag.size()&&tag[k].fi<=p[i+1].fl()) {
			int j=k; while(j<tag.size()&&tag[j].fi==tag[k].fi) cnt+=tag[j++].se;
			if(cnt==now-1) an[q[i].id]=now;
			k=j;
		}
	}
}
int main() {
	rd(n),rd(m);
	for(int i=1;i<=n;++i) {
		rd(L[i].k),rd(L[i].b);
		L[i].id=i;
	}
	sort(L+1,L+n+1);
	memset(an,-1,sizeof(an));
	for(int i=1;i<=m;++i) sol(i);
	for(int i=1;i<=n;++i) {
		if(i!=1) printf(" ");
		printf("%d",an[i]);
	}
	printf("\n");
	return 0;
} 

Posted by Pete on Tue, 31 May 2022 12:23:09 +0530