Topic Essentials

Bessie and Elsie baked N(1 < N < 10 ^ 5) pies, respectively.Bessie will rate these 2N pies, and Elsie will also rate them.Both scored a non-negative integer < 1e9.Because of their different tastes, the two scores for each school may be different.
They want to give each other gifts.Bessie started by giving Elsie a pie.When they receive a gift (the other party's pie), they always give back the other party a pie they made themselves.
They choose the same method of return.Take Elsie for example. Elsie chooses a return gift based on her score.The return score must be at least greater than the pie she received, but the difference between the two pies must not be greater than D(0 < D < 10 ^ 9).If more than one pie meets the requirements, Elsie can choose either as a return gift.

Elsie will give up if no pie meets the requirements.Bessie's choice of salutation is the same.
The gift exchange between them will continue until a cow gives up (Bad End), or a cow receives a pie she has scored as 0, when the gift exchange ends happily (Happy End).
Please note that you cannot give a pie twice or to yourself.
Bessie wants to know how many times each of her pies would have given each other at least (Bessie counts Elsie once, Elsie returns Bessie once) if she had given the pie as her first gift to Elsie before Happy End.If Happy End is not possible, output -1.

Topic Analysis

We asked for the minimum number of deliveries for each pie.Observing the data range, it is obvious that one solution is not feasible, so consider finding all at once and using the shortest path.

Consider how to build an edge. We should build the edge in the reverse direction, starting with a point of 0 for each score.The pie s of each two people should be sorted separately when building the map, which makes it easier to split the map.

(Although this algorithm may be jammed as N2, it can be passed because the subjects are lazy)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=400005;
 4 const int Inf=0x3f3f3f3f;
 5 struct Node{
 6     int bv,ev,id;
 7 }pb[MAXN],pe[MAXN];
 8 
 9 inline bool cmpb(Node x,Node y){
10     return x.bv<y.bv;
11 }
12 inline bool cmpe(Node x,Node y){
13     return x.ev<y.ev;
14 }
15 struct FboB{
16     inline bool operator()(const Node &x,const Node &y){
17         return x.bv<y.bv;
18     }
19 };
20 struct FboE{
21     inline bool operator()(const Node &x,const Node &y){
22         return x.ev<y.ev;
23     }
24 };
25 
26 struct Edge{
27     int to,nxt;
28 }e[MAXN<<4];
29 int cnt,head[MAXN<<1];
30 inline void add_edge(int u,int v){
31     e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
32 }
33 int n,d;
34 queue<int> q;
35 int dis[MAXN<<1];
36 inline void bfs(){
37     while(!q.empty()){
38         int x=q.front();
39         q.pop();
40         for(int i=head[x],y;i;i=e[i].nxt){
41             y=e[i].to;
42             if(dis[y]!=-1) continue;
43             dis[y]=dis[x]+1;
44             q.push(y);
45         }
46     }
47 }
48 int main(){
49     memset(dis,-1,sizeof(dis));
50     scanf("%d%d",&n,&d);
51     for(int i=1;i<=n;++i){
52         scanf("%d%d",&pb[i].bv,&pb[i].ev);
53         if(pb[i].ev==0){
54             dis[i]=1;
55             q.push(i);
56         }
57         pb[i].id=i;
58     }
59     for(int i=1;i<=n;++i){
60         scanf("%d%d",&pe[i].bv,&pe[i].ev);
61         if(pe[i].bv==0){
62             dis[i+n]=1;
63             q.push(i+n);
64         }
65         pe[i].id=i+n;
66     }
67     sort(pb+1,pb+n+1,cmpb);
68     sort(pe+1,pe+n+1,cmpe);
69     for(int i=1,pos;i<=n;++i){
70         Node tmp;
71         tmp.bv=pe[i].bv;
72         tmp.ev=pe[i].bv;
73         pos=lower_bound(pb+1,pb+n+1,tmp,FboB())-pb;
74         for(int j=pos;j<=n;++j){
75             if(pb[j].bv>pe[i].bv+d) break;
76             add_edge(pb[j].id,pe[i].id);
77         }
78     }
79     for(int i=1,pos;i<=n;++i){
80         Node tmp;
81         tmp.bv=pb[i].ev;
82         tmp.ev=pb[i].ev;
83         pos=lower_bound(pe+1,pe+n+1,tmp,FboE())-pe;
84         for(int j=pos;j<=n;++j){
85             if(pe[j].ev>pb[i].ev+d) break;
86             add_edge(pe[j].id,pb[i].id);
87         }
88     }
89     bfs();
90     for(int i=1;i<=n;++i)
91         printf("%d\n",dis[i]);
92     return 0;
93 }