Submission #1197126

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second

int n;
int x, y;
vector<pp> data;

int par[200010];
int R(int x){return (x==par[x])?x:(par[x]=R(par[x]));}
void unite(int x, int y){ par[R(x)]=R(y); }

int diff_max[200010];
int diff_cnt[200010];
int diff_lst[200010];

void do_diff(){
    for(int i=0; i<n; ++i){
        int w, c; tie(w, c)=data[i];
        int w_dif = y-w;
        int until=lower_bound(data.begin(), data.begin()+i, pp(w_dif+1, -1e9))-data.begin()-1;
        if(0 <= until) diff_max[c]=max(diff_max[c], until);
	}
	for(int i=0; i<n;){
        int j;
        for(j=i; j<n && data[j].y==data[i].y; ++j);
        if(j <= diff_max[data[i].y] && i) unite(i-1, j);
        i=j;
	}
	priority_queue<pp> pq;
	int diff_sum=0;
	for(int i=1; i<=n; ++i) if(diff_max[i] != -1){
        pq.push(pp(-diff_max[i], i));
        ++diff_cnt[i];
        ++diff_sum;
	}
	for(int i=0; i+1<n; ++i){
        while(pq.size() && pq.top().first == -i){
            int y=pq.top().second;
            --diff_cnt[y]; --diff_sum;
            pq.pop();
        }
        int c1=data[i].y, c2=data[i+1].y;
        int left=diff_sum;
        left -= diff_cnt[c1];
        if(c1!=c2) left -= diff_cnt[c2];
        if(left){
            unite(i, i+1);
        }
	}
	set<pp> lst;
	for(int i=1; i<=n; ++i) diff_lst[i]=-1;
	
	int first_diff=0;
	while(first_diff<n && data[0].y != data[first_diff].y) ++first_diff;
	
	for(int i=0; i<n; ++i){
        int w, c; tie(w, c)=data[i];
        int w_dif = y-w;
        int until=lower_bound(data.begin(), data.begin()+i, pp(w_dif+1, -1e9))-data.begin()-1;
        if(0 <= until){
            if(c != data[0].y){
                unite(0, i);
            } else if(first_diff <= until){
                unite(first_diff, i);
            }
        }
	}
}

vector<pp> samev[200010];
void do_same(){
    for(int i=0; i<n; ++i) samev[data[i].second].pb(pp(data[i].first, i));
    for(int i=1; i<=n; ++i){
        auto&v=samev[i];
        int n=v.size();
        int max_r=0;
        for(int i=0; i<n; ++i){
            int w_same = x-v[i].first;
            int ind=lower_bound(v.begin(), v.begin()+i, pp(w_same+1, -1e9))-v.begin()-1;
            if(0<=ind){
                max_r = max(max_r, ind);
            }
        }
        for(int i=0; i+1<max_r; ++i){
            unite(v[i].y, v[i+1].y);
        }
        for(int i=0; i<n; ++i){
            int w_same = x-v[i].first;
            int ind=lower_bound(v.begin(), v.begin()+i, pp(w_same+1, -1e9))-v.begin()-1;
            if(0<=ind){
                unite(v[i].second, v[ind].second);
            }
        }
    }
}

map<int,int> elem[200010];
int fact[200010];
int factinv[200010];
const ll mod=ll(1e9)+7;

ll Pow(ll a, ll b){
    if(b==0)return 1;
    ll ret=Pow(a, b/2);
    ret=ret*ret%mod;
    if(b&1) ret=ret*a%mod;
    return ret;
}

ll comb(int n, int r){
    return fact[n]*1LL*factinv[r]%mod*factinv[n-r]%mod;
}

int main()
{
    fact[0]=factinv[0]=1;
    for(int i=1; i<=200000; ++i){
        fact[i]=(fact[i-1]*1LL*i)%mod;
        factinv[i]=Pow(fact[i], mod-2);
    }
    
	read(n, x, y);
	data.resize(n);
	for(auto& a:data) read(a.y, a.x);
	sort(all(data));

    for(int i=0; i<n; ++i) par[i]=i;
    for(int i=1; i<=n; ++i) diff_max[i]=-1;
    
	do_diff();
	do_same();
	
	for(int i=0; i<n; ++i) elem[R(i)][data[i].y]++;
	ll ans=1;
	for(int i=0; i<n; ++i) if(i==par[i]){
        //printf("Group %d: ", i);
        auto&m=elem[i];
        int s=0;
        for(auto tmp:m){
            int c=tmp.second;
            s += c;
            ans = ans * comb(s, c) % mod;
        }
        //printf("elem %d\n", s);
	}
	
	printf("%lld\n", ans);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void read(int&)’:
./Main.cpp:6:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^
./Main.cpp: In function ‘void read(ll&)’:
./Main.cpp:7:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                                   ^

Judge Result