Submission #1197256
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
Submission Time |
|
Task |
D - Colorful Balls |
User |
Namnamseo |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
4127 Byte |
Status |
AC |
Exec Time |
228 ms |
Memory |
34724 KB |
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
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
54 ms |
18688 KB |
00_example_02.txt |
AC |
54 ms |
18688 KB |
00_example_03.txt |
AC |
54 ms |
18688 KB |
01.txt |
AC |
54 ms |
18688 KB |
02.txt |
AC |
54 ms |
18688 KB |
03.txt |
AC |
58 ms |
19072 KB |
04.txt |
AC |
54 ms |
18688 KB |
05.txt |
AC |
55 ms |
18816 KB |
06.txt |
AC |
54 ms |
18688 KB |
07.txt |
AC |
119 ms |
23944 KB |
08.txt |
AC |
54 ms |
18688 KB |
09.txt |
AC |
81 ms |
19968 KB |
10.txt |
AC |
73 ms |
19840 KB |
11.txt |
AC |
54 ms |
18688 KB |
12.txt |
AC |
54 ms |
18688 KB |
13.txt |
AC |
58 ms |
19200 KB |
14.txt |
AC |
54 ms |
18688 KB |
15.txt |
AC |
84 ms |
21432 KB |
16.txt |
AC |
110 ms |
25564 KB |
17.txt |
AC |
63 ms |
19200 KB |
18.txt |
AC |
76 ms |
20480 KB |
19.txt |
AC |
102 ms |
22656 KB |
20.txt |
AC |
199 ms |
32844 KB |
21.txt |
AC |
194 ms |
34112 KB |
22.txt |
AC |
172 ms |
33328 KB |
23.txt |
AC |
222 ms |
33156 KB |
24.txt |
AC |
171 ms |
34200 KB |
25.txt |
AC |
200 ms |
32368 KB |
26.txt |
AC |
226 ms |
32996 KB |
27.txt |
AC |
160 ms |
30848 KB |
28.txt |
AC |
228 ms |
32992 KB |
29.txt |
AC |
215 ms |
33036 KB |
30.txt |
AC |
165 ms |
34196 KB |
31.txt |
AC |
227 ms |
32988 KB |
32.txt |
AC |
177 ms |
33020 KB |
33.txt |
AC |
225 ms |
33140 KB |
34.txt |
AC |
215 ms |
32092 KB |
35.txt |
AC |
140 ms |
26240 KB |
36.txt |
AC |
164 ms |
25472 KB |
37.txt |
AC |
142 ms |
26496 KB |
38.txt |
AC |
140 ms |
25856 KB |
39.txt |
AC |
143 ms |
25600 KB |
40.txt |
AC |
224 ms |
33204 KB |
41.txt |
AC |
197 ms |
33712 KB |
42.txt |
AC |
195 ms |
34724 KB |
43.txt |
AC |
170 ms |
33836 KB |
44.txt |
AC |
224 ms |
34104 KB |
45.txt |
AC |
170 ms |
34580 KB |
46.txt |
AC |
196 ms |
33112 KB |
47.txt |
AC |
144 ms |
27120 KB |
48.txt |
AC |
148 ms |
29168 KB |
49.txt |
AC |
146 ms |
27888 KB |
50.txt |
AC |
158 ms |
29748 KB |
51.txt |
AC |
141 ms |
30708 KB |
52.txt |
AC |
145 ms |
27892 KB |
53.txt |
AC |
144 ms |
27892 KB |
54.txt |
AC |
145 ms |
27892 KB |