Submission #1674687


Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int 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();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=200005;
int X,Y,n;
struct info{
	int w,c;
	inline void init(){read(c);read(w);}
}a[maxn];
inline bool operator < (const info &a,const info &b){
	return a.c<b.c||(a.c==b.c&&a.w<b.w);
}
priority_queue<pin,vector<pin>,greater<pin> > heap;
int fa[maxn],v[maxn],id2,lv1,lv2;
int fac[maxn],facinv[maxn];
const int mod=1e9+7;
inline int powmod(int a,int b){
	int res=1;for(;b;b>>=1){
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
	}return res;
}
inline void prprpr(){
	fac[0]=1;
	rep(i,1,200000)fac[i]=1ll*fac[i-1]*i%mod;
	facinv[200000]=powmod(fac[200000],mod-2);
	per(i,200000-1,0)facinv[i]=1ll*facinv[i+1]*(i+1)%mod;
}
inline int find(int n){
	int step=n,x;
	while(step!=fa[step])step=fa[step];
	while(n!=step)x=fa[n],fa[n]=step,n=x;return n;
}
map<int,int> tot[maxn];
vector<int> wt;
inline void maintain(){
	while(heap.size()>=2){
		pin x=heap.top();heap.pop();
		pin y=heap.top();heap.pop();
		if(x.w1+y.w1<=Y){
			fa[y.w2]=x.w2;
			heap.push(x);
		}else{
			heap.push(x);
			heap.push(y);
			break;
		}
	}
}
int main(){
    prprpr();
    read(n);read(X);read(Y);
    rep(i,1,n)a[i].init();
    sort(a+1,a+1+n);
    rep(i,1,n){
    	if(a[i].c!=a[i-1].c){
    		for(int x:wt){
    			heap.push(mk(v[x],x));
    		}
    		wt.clear();
    		if(id2){
    			v[id2]=min(v[id2],lv2);
    			heap.push(mk(v[id2],id2));
    			maintain();
    			id2=0;lv1=0;lv2=0;
    		}
    	}
    	if(id2){
    		if(a[i].w+lv2<=X){
    			fa[i]=id2;
    			continue;
    		}
    		if(a[i].w+lv1<=Y){
    			fa[i]=id2;
    			continue;
    		}
    		v[i]=a[i].w;
    		fa[i]=i;
  	 		// heap.push(mk(v[i],i));
  	 		wt.pb(i);
    		continue;
    	}
    	pin x=mk(0,0);
    	if(heap.size())x=heap.top();
    	if(x==mk(0,0)){
    		v[i]=a[i].w;
    		fa[i]=i;
    		lv1=1e9;id2=i;lv2=a[i].w;
    		continue;
    	}
    	if(a[i].w+v[x.w2]<=Y){
    		id2=x.w2;fa[i]=id2;
    		lv2=a[i].w;lv1=v[id2];
    		heap.pop();
    		continue;
    	}
    	v[i]=a[i].w;
    	fa[i]=i;id2=i;lv2=a[i].w;lv1=1e9;
    }
    rep(i,1,n)tot[find(i)][a[i].c]++;
    int res=1;
    rep(i,1,n){
    	int sum=0;
    	for(pin x:tot[i]){
    		res=1ll*res*facinv[x.w2]%mod;
    		sum+=x.w2;
    	}
    	res=1ll*res*fac[sum]%mod;
    }
    printf("%d\n",res);
    return 0;
}

Submission Info

Submission Time
Task D - Colorful Balls
User Scape
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3250 Byte
Status WA
Exec Time 104 ms
Memory 25072 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 3
AC × 54
WA × 3
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 8 ms 12544 KB
00_example_02.txt AC 8 ms 12544 KB
00_example_03.txt AC 8 ms 12672 KB
01.txt AC 9 ms 12544 KB
02.txt AC 8 ms 12544 KB
03.txt AC 10 ms 12800 KB
04.txt AC 9 ms 12544 KB
05.txt AC 10 ms 12672 KB
06.txt AC 9 ms 12544 KB
07.txt AC 45 ms 16124 KB
08.txt AC 9 ms 12544 KB
09.txt AC 21 ms 13184 KB
10.txt AC 18 ms 13184 KB
11.txt AC 9 ms 12544 KB
12.txt AC 9 ms 12544 KB
13.txt AC 11 ms 12800 KB
14.txt AC 9 ms 12544 KB
15.txt AC 24 ms 14208 KB
16.txt AC 48 ms 18036 KB
17.txt AC 13 ms 12928 KB
18.txt AC 20 ms 13824 KB
19.txt AC 36 ms 15608 KB
20.txt AC 100 ms 22388 KB
21.txt AC 104 ms 23796 KB
22.txt AC 99 ms 23792 KB
23.txt AC 101 ms 21496 KB
24.txt AC 101 ms 24944 KB
25.txt AC 99 ms 21748 KB
26.txt AC 98 ms 21116 KB
27.txt AC 90 ms 21492 KB
28.txt AC 99 ms 21116 KB
29.txt AC 101 ms 21880 KB
30.txt AC 101 ms 25072 KB
31.txt AC 98 ms 21116 KB
32.txt AC 100 ms 23152 KB
33.txt AC 100 ms 21372 KB
34.txt AC 89 ms 20220 KB
35.txt WA 61 ms 16772 KB
36.txt AC 67 ms 16636 KB
37.txt WA 65 ms 16764 KB
38.txt WA 57 ms 16652 KB
39.txt AC 59 ms 16632 KB
40.txt AC 93 ms 20988 KB
41.txt AC 100 ms 22772 KB
42.txt AC 104 ms 23924 KB
43.txt AC 99 ms 24048 KB
44.txt AC 99 ms 22008 KB
45.txt AC 101 ms 24944 KB
46.txt AC 98 ms 22260 KB
47.txt AC 52 ms 17656 KB
48.txt AC 58 ms 20856 KB
49.txt AC 55 ms 18680 KB
50.txt AC 84 ms 20212 KB
51.txt AC 82 ms 20212 KB
52.txt AC 52 ms 18932 KB
53.txt AC 53 ms 18932 KB
54.txt AC 52 ms 18932 KB