QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393891 | #806. Deck Building | Diu | AC ✓ | 191ms | 14464kb | C++14 | 3.8kb | 2024-04-19 16:23:42 | 2024-04-19 16:23:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,t[N];
struct node{int x,y;}a[N];
bool cmpy(node a,node b){return a.y<b.y;}
int f[N][2],g[N][2];
struct Bit{
int vis[N],st[N],tp,c[N];
void ins(int i,int v){
for(;i<=n;i+=i&-i){
if(!vis[i])vis[i]=1,st[++tp]=i;
c[i]=(c[i]+v)%mod;
}
}
int qry(int i){
int s=0;
for(;i;i&=i-1)s=(s+c[i])%mod;
return s;
}
void clr(){
for(;tp;--tp)vis[st[tp]]=c[st[tp]]=0;
}
}T0,T1,T2,T3;
void add(int &x,int y){x=(x+y)%mod;}
struct Seg{
int s1[N<<2],s2[N<<2],tg[N<<2];
#define ls (o<<1)
#define rs (o<<1|1)
void clr(int o,int l,int r){
s1[o]=s2[o]=tg[o]=0;
if(l==r)return;
int mid=l+r>>1;
clr(ls,l,mid),clr(rs,mid+1,r);
}
void add(int o,int v){s2[o]=(s2[o]+1ll*s1[o]*v)%mod,tg[o]=(tg[o]+v)%mod;}
void down(int o){if(tg[o])add(ls,tg[o]),add(rs,tg[o]),tg[o]=0;}
void up(int o){s1[o]=(s1[ls]+s1[rs])%mod,s2[o]=(s2[ls]+s2[rs])%mod;}
void chg(int o,int l,int r,int x,int v){
if(l==r)return void(s1[o]=(s1[o]+v)%mod);
int mid=l+r>>1;down(o);
if(x<=mid)chg(ls,l,mid,x,v);
else chg(rs,mid+1,r,x,v);
up(o);
}
void upd(int o,int l,int r,int x,int y,int v){
if(x<=l&&r<=y)return add(o,v);
int mid=l+r>>1;down(o);
if(x<=mid)upd(ls,l,mid,x,y,v);
if(y>mid)upd(rs,mid+1,r,x,y,v);
up(o);
}
int qry(int o,int l,int r,int x,int y){
if(x<=l&&r<=y)return s2[o];
int mid=l+r>>1;down(o);
if(y<=mid)return qry(ls,l,mid,x,y);
if(x>mid)return qry(rs,mid+1,r,x,y);
return (qry(ls,l,mid,x,y)+qry(rs,mid+1,r,x,y))%mod;
}
}T;
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),t[i]=a[i].x;
sort(a+1,a+n+1,cmpy);
sort(t+1,t+n+1);
for(int i=1;i<=n;i++)a[i].x=lower_bound(t+1,t+n+1,a[i].x)-t;
int ans=0;
for(int i=1,l=1;i<=n;i++){
while(a[l].y<a[i].y)T0.ins(a[l].x,f[l][0]),T1.ins(n+1-a[l].x,f[l][1]),++l;
f[i][1]=(1+T0.qry(a[i].x-1))%mod;
f[i][0]=(1+T1.qry(n-a[i].x))%mod;
}
int mn=n+1,mx=0;
T0.clr(),T1.clr();
for(int i=n,l=n;i>=1;i--){
while(a[l].y>a[i].y)T0.ins(a[l].x,g[l][0]),T1.ins(n+1-a[l].x,g[l][1]),mx=max(mx,a[l].x),mn=min(mn,a[l].x),--l;
g[i][1]=((mn>=a[i].x)+T0.qry(a[i].x-1))%mod;
g[i][0]=((mx<=a[i].x)+T1.qry(n-a[i].x))%mod;
}
T0.clr(),T1.clr();
// for(int i=1;i<=n;i++){
// for(int j=i+1;j<=n;j++){
// for(int k=j+1;k<=n;k++){
// if(a[j].y==a[i].y)continue;
// if(a[j].x>a[i].x&&a[j].x<a[k].x)ans=(ans+1ll*f[i][0]*g[k][1])%mod;
// if(a[j].x<a[i].x&&a[j].x>a[k].x)ans=(ans+1ll*f[i][1]*g[k][0])%mod;
// }
// }
// }
for(int i=1,l=1;i<=n;i++){
while(a[l].y<a[i].y)T0.ins(a[l].x,f[l][0]),T1.ins(n+1-a[l].x,f[l][1]),++l;
ans=(ans+1ll*T2.qry(a[i].x-1)*g[i][1])%mod;
ans=(ans+1ll*T3.qry(n-a[i].x)*g[i][0])%mod;
T2.ins(a[i].x,T0.qry(a[i].x-1));
T3.ins(n+1-a[i].x,T1.qry(n-a[i].x));
}
// for(int i=1;i<=n;i++)printf("%d %d %d %d %d %d\n",a[i].x,a[i].y,f[i][0],f[i][1],g[i][0],g[i][1]);
// printf("%d\n",ans);
// for(int i=1;i<=n;i++){
// for(int j=i+1;j<=n;j++){
// for(int k=j+1;k<=n;k++){
// if(a[i].y==a[j].y||a[i].y==a[k].y)continue;
// if(a[i].x<a[k].x&&a[k].x<a[j].x)ans=(ans+1ll*f[i][0]*g[j][1])%mod;
// if(a[i].x>a[k].x&&a[k].x>a[j].x)ans=(ans+1ll*f[i][1]*g[j][0])%mod;
// }
// }
// }
for(int r=n,l=n;r>=1;r=l){
while(a[r].y==a[l].y)--l;
for(int i=r;i>l;i--)if(a[i].x<n)ans=(ans+1ll*f[i][0]*T.qry(1,1,n,a[i].x+1,n))%mod;
for(int i=r;i>l;i--){
if(a[i].x>1)T.upd(1,1,n,1,a[i].x-1,g[i][1]);
T.chg(1,1,n,a[i].x,1);
}
}
T.clr(1,1,n);
for(int r=n,l=n;r>=1;r=l){
while(a[r].y==a[l].y)--l;
for(int i=r;i>l;i--)if(a[i].x>1)ans=(ans+1ll*f[i][1]*T.qry(1,1,n,1,a[i].x-1))%mod;
for(int i=r;i>l;i--){
if(a[i].x<n)T.upd(1,1,n,a[i].x+1,n,g[i][0]);
T.chg(1,1,n,a[i].x,1);
}
}
printf("%d\n",ans);
}
/*
10
7 5
9 7
3 1
7 3
6 5
8 6
1 1
10 4
5 8
7 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5900kb
input:
6 8 8 5 9 9 4 3 9 3 1 7 5
output:
42
result:
ok 1 number(s): "42"
Test #2:
score: 0
Accepted
time: 1ms
memory: 6056kb
input:
10 7 5 9 7 3 1 7 3 6 5 8 6 1 1 10 4 5 8 7 4
output:
248
result:
ok 1 number(s): "248"
Test #3:
score: 0
Accepted
time: 1ms
memory: 6064kb
input:
10 4 5 1 5 3 4 2 1 1 1 2 2 5 1 2 3 2 2 2 2
output:
41
result:
ok 1 number(s): "41"
Test #4:
score: 0
Accepted
time: 0ms
memory: 6112kb
input:
10 3 3 3 1 2 1 3 1 1 3 3 1 1 3 1 1 2 1 3 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 6120kb
input:
10 1 1 2 2 1 1 1 2 2 1 1 1 2 2 1 2 2 1 2 2
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 6024kb
input:
10 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
10 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5984kb
input:
10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 0ms
memory: 5988kb
input:
10 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 1ms
memory: 6028kb
input:
10 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5964kb
input:
10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 1ms
memory: 6048kb
input:
100 575 675 185 970 773 736 611 344 757 32 973 678 835 243 439 82 141 269 257 54 850 579 311 73 1 573 413 380 179 343 817 456 591 122 544 455 224 946 461 937 974 925 910 10 714 102 144 439 443 819 78 663 50 250 625 655 123 265 232 930 333 67 94 40 540 50 893 577 90 861 647 911 812 231 452 314 619 26...
output:
35230048
result:
ok 1 number(s): "35230048"
Test #15:
score: 0
Accepted
time: 1ms
memory: 6076kb
input:
100 245 317 172 495 152 131 404 36 343 118 465 389 153 199 19 76 331 374 216 236 327 213 15 36 361 73 89 296 282 140 259 10 397 2 39 477 229 138 477 7 413 428 144 461 476 465 461 254 332 462 135 313 61 260 64 118 480 20 206 194 214 303 490 157 235 457 393 255 298 408 98 370 241 106 433 21 405 243 39...
output:
32482520
result:
ok 1 number(s): "32482520"
Test #16:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
100 55 26 27 241 327 317 95 303 22 307 85 198 179 133 66 46 103 13 235 205 214 169 232 219 317 116 53 221 10 189 222 257 130 121 13 192 145 232 79 136 260 147 323 172 203 31 263 291 282 114 4 312 166 225 242 175 160 62 204 302 50 101 171 78 173 247 95 140 240 55 275 163 49 118 245 292 201 142 45 63 ...
output:
172584922
result:
ok 1 number(s): "172584922"
Test #17:
score: 0
Accepted
time: 1ms
memory: 6068kb
input:
100 115 74 99 8 104 141 172 185 1 128 19 240 158 31 191 14 157 86 122 241 109 250 39 134 245 146 167 190 156 79 155 126 46 28 3 87 73 169 101 183 234 113 93 79 239 117 30 103 81 118 226 8 157 86 96 43 227 141 207 73 222 62 135 93 212 41 167 15 64 71 153 181 118 48 148 2 36 85 24 147 236 108 102 88 2...
output:
76646622
result:
ok 1 number(s): "76646622"
Test #18:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
100 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1...
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
100 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 ...
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
100 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 ...
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
100 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 ...
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
100 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1...
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
100 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 ...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 1ms
memory: 6048kb
input:
100 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 ...
output:
0
result:
ok 1 number(s): "0"
Test #25:
score: 0
Accepted
time: 0ms
memory: 6044kb
input:
100 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 ...
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 2ms
memory: 6108kb
input:
1000 86431 27137 49017 82657 4403 22129 75953 99764 6113 1698 95077 86630 29391 11634 31357 25802 9025 24444 10687 54697 28788 17571 6145 90923 68448 26458 32382 57601 16270 23902 5591 2429 28786 9566 61958 86342 95893 51650 98150 79987 86923 95428 12921 81930 15877 45934 79628 61347 56938 30082 488...
output:
127148540
result:
ok 1 number(s): "127148540"
Test #27:
score: 0
Accepted
time: 2ms
memory: 4100kb
input:
1000 12489 36322 34117 46134 16212 9276 27202 4612 3757 27105 21361 21483 33913 28003 31197 19766 43870 46945 20528 22018 46418 48988 40878 2779 25914 42359 40556 48757 35176 6107 44919 24489 7950 42750 38279 35706 13494 9506 17928 24375 33042 35373 6020 32586 30475 28922 3212 19565 25341 18284 1431...
output:
616326982
result:
ok 1 number(s): "616326982"
Test #28:
score: 0
Accepted
time: 2ms
memory: 4112kb
input:
1000 7323 6626 3017 4496 20228 13938 19609 12810 16769 11186 17078 23177 18070 17565 4608 16628 5597 16401 20213 20477 11312 24804 27589 17680 12379 33048 4507 6532 32892 21191 5104 5317 14239 28563 33237 9806 27828 3228 6778 29666 6687 17968 13922 32122 10048 3457 9651 20703 26908 19202 25760 10693...
output:
110646368
result:
ok 1 number(s): "110646368"
Test #29:
score: 0
Accepted
time: 2ms
memory: 6128kb
input:
1000 8630 4304 24285 17751 15734 9031 7717 20268 7221 3224 18854 19634 7652 5250 3587 4421 10047 14354 21534 3491 18742 9691 23193 3374 8898 3228 2869 20968 5470 19286 21313 19479 23256 11418 23655 6370 6266 22969 8347 11992 10455 6107 20223 13887 8566 13285 5343 19503 24115 23959 16232 24431 17885 ...
output:
231014540
result:
ok 1 number(s): "231014540"
Test #30:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
1000 100000 100000 99997 99999 99981 99998 99994 99996 99985 99991 99947 99999 99996 99987 99998 99991 99997 99960 100000 100000 99987 99986 100000 100000 99994 99984 99986 99998 99998 99998 99992 99984 99996 99999 99995 99990 99996 99995 99998 99979 99994 99990 99969 99995 99984 100000 99989 99996 ...
output:
350251835
result:
ok 1 number(s): "350251835"
Test #31:
score: 0
Accepted
time: 2ms
memory: 6116kb
input:
1000 49999 49996 49993 50000 49997 49998 49997 49995 49981 49997 49986 50000 49980 49997 49980 49994 49999 50000 49996 49991 49998 50000 50000 50000 49992 49991 49988 49999 49994 49995 50000 50000 49982 49990 49993 49999 49992 50000 49999 49995 49980 49983 49991 49998 50000 49999 49994 49992 49992 4...
output:
935812308
result:
ok 1 number(s): "935812308"
Test #32:
score: 0
Accepted
time: 2ms
memory: 6016kb
input:
1000 33331 33333 33333 33333 33323 33332 33332 33332 33332 33329 33331 33326 33327 33331 33327 33330 33331 33333 33333 33332 33329 33331 33330 33332 33333 33333 33329 33333 33333 33333 33333 33332 33328 33333 33333 33321 33329 33328 33330 33325 33333 33333 33333 33330 33333 33332 33329 33326 33332 3...
output:
877213888
result:
ok 1 number(s): "877213888"
Test #33:
score: 0
Accepted
time: 1ms
memory: 4140kb
input:
1000 25000 24997 25000 24993 24999 24998 24985 24998 24997 25000 24998 24999 24999 25000 25000 25000 25000 24999 25000 24996 24999 25000 24998 24994 24993 25000 24999 24997 24997 24999 24998 25000 25000 24998 24998 24997 25000 25000 25000 25000 24996 25000 25000 25000 25000 24998 24996 25000 24996 2...
output:
287107190
result:
ok 1 number(s): "287107190"
Test #34:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
1000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 1...
output:
0
result:
ok 1 number(s): "0"
Test #35:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
1000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000 5...
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
1000 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 3...
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
1000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 25000 2...
output:
0
result:
ok 1 number(s): "0"
Test #38:
score: 0
Accepted
time: 15ms
memory: 7036kb
input:
10000 4633775 8597356 2699037 4519097 215663 8847151 2320750 8395929 7336367 7601431 1864879 3603476 1845367 6296003 7481003 401422 4142254 2795163 2402256 5487828 5218136 2877653 4008405 6850487 4291704 853054 1723253 6936365 549740 5507031 8744244 8071696 2409813 3272852 5409543 1292012 7130213 67...
output:
994156004
result:
ok 1 number(s): "994156004"
Test #39:
score: 0
Accepted
time: 11ms
memory: 5132kb
input:
10000 3317120 2704295 1347782 1968508 2930746 1917113 504236 4582375 2837194 2945427 1384593 3437926 2576871 2829762 1798098 3027033 1728935 1644363 1513713 2132869 473110 2818288 4707455 4121234 1929294 4443287 269597 3415714 2469393 1282225 401423 3513111 3821928 4261297 4078894 3400547 1754622 18...
output:
754467671
result:
ok 1 number(s): "754467671"
Test #40:
score: 0
Accepted
time: 15ms
memory: 6972kb
input:
10000 647671 647122 1385864 495941 223766 1597629 1774742 849800 1633893 1391981 2412857 1306832 934100 2621512 1785173 3231179 3068092 2172748 200575 26528 505108 1749504 483932 326612 2688415 1530130 820201 2289847 257156 3201426 3088374 3324084 659379 2093447 37912 3328032 859197 998356 2679240 1...
output:
518503569
result:
ok 1 number(s): "518503569"
Test #41:
score: 0
Accepted
time: 11ms
memory: 6836kb
input:
10000 881094 106360 2253866 1844442 105079 2114443 658140 1430300 220357 1231055 821812 1982473 1501692 2032373 274789 546351 1600257 821306 1089552 1484873 2269705 1362271 29556 681917 1481631 2261800 1484462 1796278 2101356 1133104 1024552 1292420 1666079 768427 2256354 1771456 1175505 480924 2741...
output:
19228350
result:
ok 1 number(s): "19228350"
Test #42:
score: 0
Accepted
time: 15ms
memory: 6704kb
input:
10000 9997144 9999867 9999401 9996588 9999828 9999461 9999661 9998588 9998187 9998304 9997984 9999422 9998824 9999722 9999255 9999658 9996263 9999219 9999416 9999209 9999041 9998602 9999214 9998617 9998943 9999701 9999522 9999798 9998448 9999930 9996429 9999580 9999486 9997339 9999960 9996709 999948...
output:
838434975
result:
ok 1 number(s): "838434975"
Test #43:
score: 0
Accepted
time: 15ms
memory: 6920kb
input:
10000 4999890 4998903 4999577 4999338 4999896 4999718 4999559 4999823 4999684 4999997 4997606 4999583 4999730 4999993 4999931 4999611 4998354 4999531 4999616 4999360 4999979 4999716 4999694 4999912 4999405 4999973 4999716 4998983 4999968 4999814 4999587 4999827 4999029 4999799 4999023 4999919 499888...
output:
464551882
result:
ok 1 number(s): "464551882"
Test #44:
score: 0
Accepted
time: 11ms
memory: 6924kb
input:
10000 3333274 3333105 3333095 3329953 3332699 3333114 3332996 3333054 3333029 3333128 3333322 3332939 3332762 3333304 3333277 3332900 3333272 3333327 3332495 3332651 3333192 3333133 3333243 3333096 3333068 3332968 3333077 3332560 3332365 3332365 3333312 3333228 3333234 3333110 3333052 3333199 333332...
output:
218915367
result:
ok 1 number(s): "218915367"
Test #45:
score: 0
Accepted
time: 14ms
memory: 4932kb
input:
10000 2499507 2499792 2499967 2499407 2499665 2499668 2499992 2499703 2499746 2499661 2499596 2499583 2499815 2499932 2499985 2499445 2499692 2499964 2499918 2499745 2499786 2499552 2499956 2499460 2499902 2499493 2499622 2499769 2499498 2499854 2499961 2499624 2499850 2499824 2499956 2499719 249940...
output:
860360090
result:
ok 1 number(s): "860360090"
Test #46:
score: 0
Accepted
time: 7ms
memory: 4620kb
input:
10000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 100000...
output:
0
result:
ok 1 number(s): "0"
Test #47:
score: 0
Accepted
time: 6ms
memory: 4640kb
input:
10000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 5000000 500000...
output:
0
result:
ok 1 number(s): "0"
Test #48:
score: 0
Accepted
time: 7ms
memory: 6488kb
input:
10000 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 3333333 333333...
output:
0
result:
ok 1 number(s): "0"
Test #49:
score: 0
Accepted
time: 7ms
memory: 6544kb
input:
10000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 2500000 250000...
output:
0
result:
ok 1 number(s): "0"
Test #50:
score: 0
Accepted
time: 189ms
memory: 14464kb
input:
100000 623377866 697537747 573943930 296823237 412122312 398624791 195063406 447660985 700804527 591218887 780764693 200117648 33323700 816830804 586609247 17063332 759063345 932921267 157105512 254012739 330234770 344729696 349739024 289796077 528283689 876523370 68064908 225047998 380316114 377459...
output:
664448192
result:
ok 1 number(s): "664448192"
Test #51:
score: 0
Accepted
time: 187ms
memory: 14448kb
input:
100000 477236688 274270881 75512389 381338264 268546489 90529791 239239865 30413580 405724069 424507117 211538 394581460 364085513 93403504 331255818 281517105 143501005 389725179 333242328 484914868 353566682 391400004 392079248 145470044 151324182 10663680 392308481 393445383 19247268 222766802 52...
output:
438214323
result:
ok 1 number(s): "438214323"
Test #52:
score: 0
Accepted
time: 190ms
memory: 14380kb
input:
100000 306742422 198691299 94945898 24711633 240409441 97109990 145093548 185317406 160866893 108246006 212906624 181558823 146768837 246801410 116831329 164686983 116593327 182891824 127536726 227454139 239656160 198237037 147234181 211790223 104690453 52160171 272941073 260823924 9056270 38344660 ...
output:
148710807
result:
ok 1 number(s): "148710807"
Test #53:
score: 0
Accepted
time: 183ms
memory: 14320kb
input:
100000 186830280 132235239 110039815 90708227 224329961 214594596 60336660 142916111 47041019 139112994 64261225 78488165 6356344 68866678 112425342 70361439 219826635 87859360 230407921 4518496 203708772 82811700 64772512 54917419 155012931 151702523 154078249 17256074 173886866 68082812 125329142 ...
output:
271631804
result:
ok 1 number(s): "271631804"
Test #54:
score: 0
Accepted
time: 180ms
memory: 14220kb
input:
100000 999978924 999970447 999924992 999919480 999918687 999977571 999962735 999897303 999971470 999904210 999899702 999787875 999969808 999957752 999880154 999952444 999923599 999959250 999954964 999812873 999699727 999997476 999992342 999891767 999973952 999769171 999878976 999975388 999981423 999...
output:
66061962
result:
ok 1 number(s): "66061962"
Test #55:
score: 0
Accepted
time: 187ms
memory: 14024kb
input:
100000 499985588 499971054 499987470 499990535 499800706 499992334 499947598 499897217 499996228 499919723 499962622 499936048 499866481 499972479 499979992 499906956 499870941 499877492 499996460 499971587 499998715 499957481 499826949 499976811 499958984 499979321 499900189 499920583 499970963 499...
output:
327617850
result:
ok 1 number(s): "327617850"
Test #56:
score: 0
Accepted
time: 191ms
memory: 14092kb
input:
100000 333282757 333309497 333305203 333321466 333332172 333309032 333320925 333320267 333312926 333251790 333328649 333329333 333326685 333259458 333309966 333295268 333317724 333319255 333332528 333189023 333274234 333325788 333312674 333300114 333301256 333303880 333245259 333325424 333308391 333...
output:
205900314
result:
ok 1 number(s): "205900314"
Test #57:
score: 0
Accepted
time: 190ms
memory: 13876kb
input:
100000 249961607 249978117 249982122 249887450 249994649 249999889 249966799 249963230 249978853 249939722 249995489 249987215 249987126 249999678 249980742 249966414 249929352 249988733 249987539 249980371 249975774 249995402 249985705 249957668 249991749 249998810 249999276 249996444 249990683 249...
output:
934908687
result:
ok 1 number(s): "934908687"
Test #58:
score: 0
Accepted
time: 123ms
memory: 11852kb
input:
100000 999999991 999999980 1000000000 1000000000 999999974 999999999 999999999 999999996 999999988 999999980 999999996 999999958 999999984 999999977 999999989 999999967 999999961 999999981 999999991 999999985 1000000000 999999996 999999962 999999972 999999980 999999990 999999997 1000000000 999999987...
output:
19335671
result:
ok 1 number(s): "19335671"
Test #59:
score: 0
Accepted
time: 118ms
memory: 11124kb
input:
100000 499999999 499999994 499999997 499999993 499999994 499999998 499999987 499999987 499999994 499999998 499999999 499999993 499999998 499999996 499999996 499999998 499999988 499999999 499999997 499999995 500000000 499999990 499999997 500000000 500000000 499999994 499999995 499999990 500000000 499...
output:
604812104
result:
ok 1 number(s): "604812104"
Test #60:
score: 0
Accepted
time: 111ms
memory: 11108kb
input:
100000 333333330 333333333 333333333 333333331 333333333 333333333 333333332 333333330 333333333 333333331 333333333 333333332 333333330 333333332 333333333 333333326 333333331 333333328 333333327 333333333 333333333 333333332 333333330 333333323 333333333 333333333 333333330 333333330 333333333 333...
output:
700912328
result:
ok 1 number(s): "700912328"
Test #61:
score: 0
Accepted
time: 112ms
memory: 10884kb
input:
100000 249999996 249999997 249999999 249999997 250000000 249999999 249999998 250000000 249999998 249999999 250000000 250000000 250000000 249999997 249999999 250000000 249999999 249999995 250000000 250000000 249999994 249999999 250000000 250000000 249999997 249999997 249999998 249999994 250000000 249...
output:
596030453
result:
ok 1 number(s): "596030453"
Test #62:
score: 0
Accepted
time: 66ms
memory: 9856kb
input:
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0
result:
ok 1 number(s): "0"
Test #63:
score: 0
Accepted
time: 101ms
memory: 10732kb
input:
100000 1 2 2 1 1 1 2 3 1 1 4 1 2 1 1 1 1 3 1 3 1 1 1 3 2 2 2 4 4 1 1 1 1 1 4 2 1 6 5 4 3 1 1 2 1 1 2 3 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 2 4 3 2 3 1 1 2 2 1 2 6 2 3 4 2 2 1 3 6 3 3 2 1 1 4 1 5 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 2 1 5 1 1 5 1 1 4 3 2 2 2 2 1 3 3 4 4 2 5 1 2 4 3 1 2 1 2 3 1 2 4 2 1 4 1 3 1 1...
output:
803482549
result:
ok 1 number(s): "803482549"
Test #64:
score: 0
Accepted
time: 109ms
memory: 10564kb
input:
100000 1 1 3 2 3 1 1 1 5 1 1 1 1 4 2 3 2 3 1 10 3 3 4 1 2 1 3 2 3 1 1 3 2 1 4 1 3 1 9 3 1 2 6 5 4 3 1 3 9 1 1 5 4 3 3 1 1 2 4 5 3 2 1 4 2 3 4 1 1 1 1 1 5 3 1 2 1 2 3 6 2 1 3 1 1 5 1 5 8 1 1 1 6 2 1 2 3 7 1 5 4 1 1 2 4 3 3 2 6 5 1 1 2 3 3 7 9 2 1 5 2 5 1 8 4 1 1 5 1 7 2 1 2 1 2 1 1 3 1 2 1 4 3 7 5 6 ...
output:
906006427
result:
ok 1 number(s): "906006427"
Test #65:
score: 0
Accepted
time: 114ms
memory: 10928kb
input:
100000 2 4 7 1 7 2 11 1 5 2 10 2 1 9 1 1 3 1 1 5 2 6 2 1 6 3 1 2 3 11 4 10 13 9 3 6 7 3 4 2 16 3 6 2 1 2 2 2 6 7 2 3 3 4 2 2 2 8 10 2 2 2 5 8 15 3 5 1 1 1 1 3 1 1 1 3 4 3 5 5 7 1 2 5 1 2 5 4 1 6 4 1 6 2 1 3 2 1 11 1 3 1 3 2 8 4 3 3 1 12 1 10 3 5 19 6 10 4 15 2 2 1 7 1 4 3 8 1 1 2 5 1 3 1 4 1 3 9 3 2...
output:
841303839
result:
ok 1 number(s): "841303839"
Test #66:
score: 0
Accepted
time: 112ms
memory: 11360kb
input:
100000 1 1 1 6 2 6 4 7 5 1 4 1 8 12 2 1 1 3 12 3 9 8 6 5 27 1 5 2 1 2 3 6 8 3 7 2 4 1 5 14 7 3 1 1 1 3 5 12 2 1 6 1 3 9 7 4 9 8 16 7 11 11 3 5 6 8 2 6 3 2 1 1 1 4 1 4 9 1 5 4 13 7 9 2 8 2 2 1 1 2 5 3 3 1 6 1 2 5 2 8 1 4 2 1 7 3 4 2 1 2 13 4 4 2 11 11 6 1 3 1 2 10 5 17 2 7 11 3 5 2 4 15 2 1 16 3 3 10...
output:
514708189
result:
ok 1 number(s): "514708189"
Test #67:
score: 0
Accepted
time: 115ms
memory: 11340kb
input:
100000 7 6 6 11 1 6 1 6 1 21 9 1 2 14 5 7 1 16 1 6 12 6 2 5 11 1 19 16 16 3 17 4 6 4 8 2 3 10 7 2 5 2 14 16 13 3 6 6 2 1 1 8 9 4 1 4 12 8 5 1 8 1 8 1 5 3 15 5 5 6 5 4 8 3 2 2 7 3 6 5 3 19 14 2 1 30 16 2 5 3 28 2 3 3 26 3 6 6 6 4 3 4 15 1 3 1 5 3 2 3 8 11 15 1 14 1 8 7 9 1 7 3 2 1 5 13 6 3 10 2 5 1 6...
output:
90259865
result:
ok 1 number(s): "90259865"
Test #68:
score: 0
Accepted
time: 122ms
memory: 11480kb
input:
100000 22 1 9 1 12 1 6 10 7 6 4 1 1 20 2 12 6 1 5 11 11 2 4 6 6 3 9 8 18 2 5 5 2 3 11 3 6 7 13 12 7 3 14 8 5 9 6 5 9 1 8 11 13 2 2 23 9 6 4 18 30 15 4 8 2 4 2 28 23 19 4 1 10 5 8 17 6 1 1 29 8 4 6 9 8 4 23 1 22 1 1 3 20 7 8 12 4 2 7 2 2 13 9 8 1 9 11 9 5 14 9 7 5 13 1 4 1 6 2 1 7 14 5 9 14 4 6 3 5 1...
output:
629120432
result:
ok 1 number(s): "629120432"
Test #69:
score: 0
Accepted
time: 122ms
memory: 11496kb
input:
100000 4 8 15 20 4 18 9 8 9 9 4 3 9 2 21 17 3 4 2 3 1 3 6 1 3 2 1 4 8 1 7 7 10 7 4 7 1 11 17 5 10 3 1 6 4 5 1 4 6 2 10 11 6 10 2 2 1 12 27 1 1 2 14 6 5 12 37 3 50 4 25 4 6 7 9 3 6 9 16 17 17 2 15 3 8 16 8 28 2 1 2 11 3 2 5 2 33 7 11 6 12 15 52 14 13 4 1 1 4 12 14 16 4 7 11 3 3 9 6 15 10 3 11 14 4 18...
output:
153119847
result:
ok 1 number(s): "153119847"
Test #70:
score: 0
Accepted
time: 125ms
memory: 11512kb
input:
100000 1 7 6 6 14 12 14 7 26 6 6 3 1 37 8 21 13 9 9 14 2 10 7 14 15 6 1 8 3 6 1 23 23 9 2 6 7 3 4 5 7 9 2 6 2 9 28 1 7 2 2 14 5 26 1 32 6 10 32 5 29 6 13 5 6 3 13 3 17 28 7 9 4 6 12 1 1 4 26 3 2 17 4 2 4 1 3 5 1 2 15 6 24 8 1 3 12 4 4 8 5 11 9 8 2 19 2 21 1 12 13 10 3 17 7 19 13 8 22 10 12 18 9 8 4 ...
output:
616989316
result:
ok 1 number(s): "616989316"
Test #71:
score: 0
Accepted
time: 123ms
memory: 11740kb
input:
100000 24 11 2 1 15 20 29 26 2 3 5 16 4 4 1 3 10 45 4 2 9 21 5 9 10 7 12 4 6 12 13 3 15 27 1 10 6 5 23 10 13 17 15 5 1 3 8 8 28 11 15 1 8 6 2 9 11 6 1 2 32 3 21 8 2 10 17 4 2 13 9 3 2 7 4 2 3 4 8 17 1 4 18 2 5 5 6 12 14 2 7 43 4 1 1 21 2 4 14 10 1 12 26 9 1 2 4 1 3 4 12 33 6 21 1 11 1 4 13 6 18 2 11...
output:
724854696
result:
ok 1 number(s): "724854696"
Test #72:
score: 0
Accepted
time: 2ms
memory: 7952kb
input:
1 42 42
output:
0
result:
ok 1 number(s): "0"