Submission #1867043

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

map<int,set<ii> > R;
map<int,set<ii> > C;
map<int,vector<int> > rows;
map<int,vector<int> > cols;
ii pt[111111];
ll ans;

int calcrow(int x, int l, int r)
{
	if(rows.find(x)==rows.end()) return 0;
	int lb = lower_bound(rows[x].begin(),rows[x].end(),l)-rows[x].begin();
	int rb = lower_bound(rows[x].begin(),rows[x].end(),r+1)-rows[x].begin();
	return rb-lb;
}

int calccol(int x, int l, int r)
{
	if(cols.find(x)==cols.end()) return 0;
	int lb = lower_bound(cols[x].begin(),cols[x].end(),l)-cols[x].begin();
	int rb = lower_bound(cols[x].begin(),cols[x].end(),r+1)-cols[x].begin();
	return rb-lb;
}

int d=0;
bool vis[111111];

void process(int u)
{
	vis[u]=1;
	int x=pt[u].fi; int y=pt[u].se;
	ans+=calcrow(x-d,y-d,y+d);
	ans+=calcrow(x+d,y-d,y+d);
	ans+=calccol(y-d,x-d+1,x+d-1);
	ans+=calccol(y+d,x-d+1,x+d-1);
	vi Q;
	if(!R[x-d].empty())
	{
		auto it = R[x-d].lower_bound(mp(y-d,-1));
		while(it!=R[x-d].end())
		{
			if((*it).fi<=y+d)
			{
				Q.pb((*it).se); it++;
				//C[(*it).se].erase(mp(x-d,(*it).se));
				//it=R[x-d].erase(it);				
			}
			else break;
		}
	}
	if(!R[x+d].empty())
	{
		auto it = R[x+d].lower_bound(mp(y-d,-1));
		while(it!=R[x+d].end())
		{
			if((*it).fi<=y+d)
			{
				Q.pb((*it).se);
				//C[(*it).se].erase(mp(x+d,(*it).se));
				it++;			
			}
			else break;
		}
	}
	if(!C[y+d].empty())
	{
		auto it = C[y+d].lower_bound(mp(x-d+1,-1));
		while(it!=C[y+d].end())
		{
			if((*it).fi<=x+d-1)
			{
				Q.pb((*it).se);
				//R[(*it).se].erase(mp(y+d,(*it).se));
				it++;			
			}
			else break;
		}
	}
	if(!C[y-d].empty())
	{
		auto it = C[y-d].lower_bound(mp(x-d+1,-1));
		while(it!=C[y-d].end())
		{
			if((*it).fi<=x+d-1)
			{
				Q.pb((*it).se);
				//R[(*it).se].erase(mp(y-d,(*it).se));
				//it=C[y-d].erase(it);				
				it++;
			}
			else break;
		}
	}
	for(int i=0;i<Q.size();i++) 
	{
		if(!vis[Q[i]]) process(Q[i]);
	}
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,s1,s2; cin>>n>>s1>>s2; s1--; s2--;
	for(int i=0;i<n;i++)
	{
		int x,y; cin>>x>>y;
		int px,py; px=x-y; py=x+y;
		pt[i].fi=px; pt[i].se=py;
		rows[px].pb(py); cols[py].pb(px);
		if(i!=s1) 
		{
			R[px].insert(mp(py,i)); C[py].insert(mp(px,i));
		}
	}
	for(auto it = rows.begin(); it != rows.end(); it++)
	{
		sort(it->se.begin(), it->se.end());
	}
	for(auto it = cols.begin(); it != cols.end(); it++)
	{
		sort(it->se.begin(), it->se.end());
	}
	d=max(abs(pt[s1].fi-pt[s2].fi),abs(pt[s1].se-pt[s2].se));
	process(s1);
	ans>>=1;
	cout<<ans<<'\n';
}

Submission Info

Judge Result