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 |
|
|
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 |