Submission #949094

#	Time	Username	Problem	Language	Result	Execution time	Memory
949094		MilosMilutinovic	IOI Fever (JOI21_fever)	C++14	25 / 100	731 ms	524288 KiB

fever

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
    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*10+ch-'0';ch=getchar();}
    return x*f;
}

#define info pair<pair<ll,int>,pair<ll,int>>
 
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int n,tot;
int d1[100005],d2[100005],root[2][100005],lch[10000005],rch[10000005],pos[2][100005];
ll x[100005],y[100005],dir[100005];
bool vis[100005];
pair<ll,int> mn[10000005][2],mx[10000005][2];

void change(int&id,int t,int l,int r,int ql,int qr,info v){
	if(!id) id=++tot,mn[id][t]=mp((ll)1e18,0),mx[id][t]=mp((ll)-1e18,0);
	if(ql<=l&&r<=qr){
		mn[id][t]=min(mn[id][t],v.fi);
		mx[id][t]=max(mx[id][t],v.se);
		return;
	}
	int mid=(l+r)/2;
	if(qr<=mid) change(lch[id],t,l,mid,ql,qr,v);
	else if(ql>mid) change(rch[id],t,mid+1,r,ql,qr,v);
	else change(lch[id],t,l,mid,ql,qr,v),change(rch[id],t,mid+1,r,ql,qr,v);
}

pair<ll,int> query(int id,int t,int l,int r,int i,int v){
	if(!id) return mp((ll)1e18,0);
	if(l==r) return min(mp(mn[id][t].fi-v,mn[id][t].se),mp(v-mx[id][t].fi,mx[id][t].se));
	int mid=(l+r)/2;
	pair<ll,int> bst;
	if(i<=mid) bst=query(lch[id],t,l,mid,i,v);
	else bst=query(rch[id],t,mid+1,r,i,v);
	bst=min(bst,min(mp(mn[id][t].fi-v,mn[id][t].se),mp(v-mx[id][t].fi,mx[id][t].se)));
	return bst;
}
 
int main(){
	n=readint();
	for(int i=1;i<=n;i++) x[i]=readint(),y[i]=readint(),x[i]*=2,y[i]*=2;
	vector<int> xs1,xs2;
	for(int i=1;i<=n;i++){
		xs1.pb(x[i]+y[i]);
		xs2.pb(x[i]-y[i]);
	}
	sort(xs1.begin(),xs1.end());
	xs1.erase(unique(xs1.begin(),xs1.end()),xs1.end());
	sort(xs2.begin(),xs2.end());
	xs2.erase(unique(xs2.begin(),xs2.end()),xs2.end());
	int sz1=(int)xs1.size(),sz2=(int)xs2.size();
	vector<set<pii>> st1(sz1),st2(sz2);
	vector<vector<int>> ids1(sz1),ids2(sz2);
	for(int i=1;i<=n;i++){
		d1[i]=(int)(lower_bound(xs1.begin(),xs1.end(),x[i]+y[i])-xs1.begin());
		d2[i]=(int)(lower_bound(xs2.begin(),xs2.end(),x[i]-y[i])-xs2.begin());
		st1[d1[i]].emplace(x[i],i);
		st2[d2[i]].emplace(x[i],i);
		ids1[d1[i]].pb(i);
		ids2[d2[i]].pb(i);
	}
	for(int i=0;i<sz1;i++){
		sort(ids1[i].begin(),ids1[i].end(),[&](int i,int j){return x[i]<x[j];});
		for(int j=0;j<(int)ids1[i].size();j++){
			pos[0][ids1[i][j]]=j;
		}
	}
	for(int i=0;i<sz2;i++){
		sort(ids2[i].begin(),ids2[i].end(),[&](int i,int j){return x[i]<x[j];});
		for(int j=0;j<(int)ids2[i].size();j++){
			pos[1][ids2[i][j]]=j;
		}
	}
	int ans=0;
	for(int d=0;d<4;d++){
		for(int i=1;i<=n;i++) vis[i]=false;
		dir[1]=d;
		priority_queue<pair<ll,pii>> pq;
		pq.push(mp(0,mp(1,d)));
		for(int i=1;i<=n;i++){
			st1[d1[i]].emplace(x[i],i);
			st2[d2[i]].emplace(x[i],i);
		}
		while(tot){
			for(int j=0;j<2;j++){
				mn[tot][j]=mp((ll)1e18,0);
				mx[tot][j]=mp((ll)-1e18,0);
			}
			lch[tot]=0;
			rch[tot]=0;
			tot--;
		}
		for(int j=0;j<2;j++){
			for(int i=0;i<sz1;i++) root[j][i]=0;
			for(int i=0;i<sz2;i++) root[j][i]=0;
		}
		auto upd=[&](int idx){
			if(vis[idx]) return;
			pair<ll,int> bst=min(query(root[0][d1[idx]],0,0,ids1[d1[idx]].size()-1,pos[0][idx],x[idx]),query(root[1][d2[idx]],1,0,ids2[d2[idx]].size()-1,pos[1][idx],x[idx]));
			if(bst.fi<(ll)1e17){
				pq.push(mp(-bst.fi,mp(idx,bst.se)));
			}
			return;
		};
		while(!pq.empty()){
			ll t=-pq.top().fi;
			int i=pq.top().se.fi;
			int dd=pq.top().se.se;
			pq.pop();
			if(vis[i]) continue;
			dir[i]=dd;
			vis[i]=true;
			auto it1=st1[d1[i]].lower_bound(mp(x[i],i));
			if(it1!=st1[d1[i]].begin()) upd(prev(it1)->se);
			if(it1!=prev(st1[d1[i]].end())) upd(next(it1)->se);
			st1[d1[i]].erase(it1);
			auto it2=st2[d2[i]].lower_bound(mp(x[i],i));
			if(it2!=st2[d2[i]].begin()) upd(prev(it2)->se);
			if(it2!=prev(st2[d2[i]].end())) upd(next(it2)->se);
			st2[d2[i]].erase(it2);
			if(dir[i]==0){
				// up
				{
					int low=0,high=ids1[d1[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids1[d1[i]][mid]]>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					if(p!=-1){
						change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,0,p,mp(mp(x[i],2),mp((ll)-1e18,0)));
						auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]+1));
						if(it!=st1[d1[i]].begin()) upd(prev(it)->se);
					}
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids2[d2[i]][mid]]-x[i]>=t) p=mid,high=mid-1; 
						else low=mid+1;
					}
					if(p<(int)ids2[d2[i]].size()){
						change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,p,ids2[d2[i]].size()-1,mp(mp((ll)1e18,0),mp(x[i],3)));
						auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]));
						if(it!=st2[d2[i]].end()) upd(it->se);
					}
				}
			}
			if(dir[i]==1){
				// down
				{
					int low=0,high=ids1[d1[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids1[d1[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					if(p<(int)ids1[d1[i]].size()){
						change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,p,ids1[d1[i]].size()-1,mp(mp((ll)1e18,2),mp(x[i],3)));
						auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]));
						if(it!=st1[d1[i]].end()) upd(it->se);
					}
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids2[d2[i]][mid]]>=t) p=mid,low=mid+1; 
						else high=mid-1;
					}
					if(p!=-1){
						change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,0,p,mp(mp(x[i],2),mp((ll)-1e18,3)));
						auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]+1));
						if(it!=st2[d2[i]].begin()) upd(prev(it)->se);
					}
				}
			}
			if(dir[i]==2){
				// right
				{
					int low=0,high=ids1[d1[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids1[d1[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					if(p<(int)ids1[d1[i]].size()){
						change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,p,ids1[d1[i]].size()-1,mp(mp((ll)1e18,2),mp(x[i],0)));
						auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]));
						if(it!=st1[d1[i]].end()) upd(it->se);
					}
					//for(int j=p;j<(int)ids1[d1[i]].size();j++) pq.push(mp(-(x[ids1[d1[i]][j]]-x[i]),mp(ids1[d1[i]][j],0)));
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids2[d2[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					for(int j=p;j<(int)ids2[d2[i]].size();j++) pq.push(mp(-(x[ids2[d2[i]][j]]-x[i]),mp(ids2[d2[i]][j],1)));
				}
			}
			if(dir[i]==3){
				// left
				{
					int low=0,high=ids1[d1[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids1[d1[i]][mid]]>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					for(int j=0;j<=p;j++) pq.push(mp(-(x[i]-x[ids1[d1[i]][j]]),mp(ids1[d1[i]][j],1)));
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids2[d2[i]][mid]]>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					for(int j=0;j<=p;j++) pq.push(mp(-(x[i]-x[ids2[d2[i]][j]]),mp(ids2[d2[i]][j],0)));
				}
			}
		}
		int cnt=0;
		for(int i=1;i<=n;i++) cnt+=vis[i];
		ans=max(ans,cnt);
	}
	printf("%d\n",ans);
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31