QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#381836 | #7436. Optimal Ordered Problem Solver | Qingyu | 100 ✓ | 1992ms | 109868kb | C++23 | 9.3kb | 2024-04-07 20:53:58 | 2024-04-07 21:44:37 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<r;++i)
#define Fe(i,l,r) for(int i=l;i<=r;++i)
#define Fer(i,l,r) for(int i=l;i>=r;--i)
#if 0
#define pr(...) fprintf(stderr,__VA_ARGS__)
#else
#define pr(...) void(0)
#endif
typedef long long i64;
const int maxn=1e6,maxm=1e6,N=maxn+10;
namespace IO{
const int BUF_SZ=1<<16;
char ib[BUF_SZ+1],*ip=ib+BUF_SZ;
void ipre(int n){
int c=ib+BUF_SZ-ip;
if(c<n){
memcpy(ib,ip,c);
ip=ib;
fread(ib+c,1,BUF_SZ-c,stdin)[ib+c]=0;
}
}
template<class T>
T read(T L,T R){
ipre(100);
T x=0,f=1;
while(*ip<'0'||*ip>'9')if(*ip++=='-')f=-f;
while(*ip>='0'&&*ip<='9')x=x*10+*ip++-'0';
x*=f;
if(!(L<=x&&x<=R)){
std::cerr<<x<<" not in ["<<L<<","<<R<<"]\n";
exit(1);
}
return x;
}
char ob[BUF_SZ+1],*op=ob;
void opre(int n){
int c=ob+BUF_SZ-op;
if(c<n){
fwrite(ob,1,BUF_SZ-c,stdout);
op=ob;
}
}
template<class T>
void write(T x){
opre(100);
char ss[100],*sp=ss;
if(x<T(0))x=-x,*op++='-';
do *sp++=x%10+'0';while(x/=10);
while(sp!=ss)*op++=*--sp;
}
template<class T>
void write(T x,char c){
write(x);
*op++=c;
}
struct __{
__(){}
~__(){
fwrite(ob,1,op-ob,stdout);
}
}_;
};
using IO::read;
using IO::write;
const int MEM=1<<26;
char pool[MEM],*pool_p=pool;
template<class T>
void alloc(T *&p,int sz,bool init=1){
//p=new T[sz]();
//return;
p=reinterpret_cast<T*>(pool_p);
pool_p+=(sz*sizeof(T)+7)&~7;
assert(pool_p<pool+MEM);
if(init)F(i,0,sz)new(p+i)T();
}
template<class T>
struct Undo{
T &x;
T x0;
Undo(T &x):x(x),x0(x){}
~Undo(){x=x0;}
};
#define alloc_scope Undo<char*> _##__LINE__(pool_p)
struct Void{
char _[0];
template<class T>
friend void operator*=(T &,Void){}
friend Void operator+(Void,Void){return Void();}
};
template<class D=Void,class M=Void>
struct MSegTree{
struct Node{
D d;
M m;
void app(const M &t){
d*=t;
m*=t;
}
void up(const Node &a,const Node &b){
d=a.d+b.d;
d*=m;
}
}*tr;
int mx;
int n;
void in(int x){assert(1<=x&&x<=n);}
void in(int l,int r){assert(1<=l&&l<=r&&r<=n);}
void alloc(int n){
for(mx=1;mx<n+2;mx<<=1);
::alloc(tr,mx+n+3);
this->n=n;
}
void init(int n,D d0){
alloc(n);
Fe(i,1,n)tr[mx+i].d=d0;
range_update(1,n);
}
template<class T>
void init(int n,T *d0){
alloc(n);
Fe(i,1,n)tr[mx+i].d=d0[i];
range_update(1,n);
}
Node &at(int x){
in(x);
return tr[mx+x];
}
D &operator[](int x){
in(x);
return tr[mx+x].d;
}
void range_update(int l,int r){
in(l),in(r);
l+=mx,r+=mx;
for(l>>=1,r>>=1;l<r;l>>=1,r>>=1){
Fe(x,l,r)up(x);
}
for(;l;l>>=1)up(l);
}
void up(int x){
tr[x].up(tr[x*2],tr[x*2+1]);
}
void add(int x,const D &y){//M=Void
in(x);
for(x+=mx;x;x>>=1)tr[x].d=tr[x].d+y;;
}
void update(const M &t){
tr[1].app(t);
}
template<class T>
void update(int x,T y){
in(x);
for(tr[x+=mx].d=y;x>1;up(x>>=1));
}
void update(int l,int r,const M &t){
in(l),in(r);
for(l+=mx-1,r+=mx+1;l^r^1;up(l>>=1),up(r>>=1)){
if(~l&1)tr[l+1].app(t);
if(r&1)tr[r-1].app(t);
}
for(;l>1;up(l>>=1));
}
void update_prefix(int x,const M &t){
in(x);
for(x+=mx+1;x>1;up(x>>=1)){
if(x&1)tr[x-1].app(t);
}
}
void update_suffix(int x,const M &t){
in(x);
for(x+=mx-1;x>1;up(x>>=1)){
if(~x&1)tr[x+1].app(t);
}
}
D query(){
return tr[1].d;
}
D query(int l,int r){
in(l),in(r);
assert(l<=r);
D a1,a2;
for(l+=mx-1,r+=mx+1;l^r^1;a1*=tr[l>>=1].m,a2*=tr[r>>=1].m){
if(~l&1)a1=a1+tr[l+1].d;
if(r&1)a2=tr[r-1].d+a2;
}
a1=a1+a2;
for(;l>1;a1*=tr[l>>=1].m);
return a1;
}
D query_prefix(int r){
in(r);
D a1;
for(r+=mx+1;r>1;r>>=1,a1*=tr[r].m){
if(r&1)a1=tr[r-1].d+a1;
}
return a1;
}
D query_suffix(int l){
in(l);
D a1;
for(l+=mx-1;l>1;l>>=1,a1*=tr[l].m){
if(~l&1)a1=a1+tr[l+1].d;
}
return a1;
}
void dn(int x){
tr[x*2].app(tr[x].m);
tr[x*2+1].app(tr[x].m);
tr[x].m=M();
}
void dna(int x){
in(x);
x+=mx;
for(int c=__builtin_ctz(mx);c>0;--c)dn(x>>c);
}
void dna(int l,int r){
in(l,r);
l+=mx,r+=mx;
for(int c=__builtin_ctz(mx);c>0;--c){
int L=l>>c,R=r>>c;
Fe(i,L,R)dn(i);
}
}
void dna(){
F(i,1,mx){
tr[i*2].app(tr[i].m);
tr[i*2+1].app(tr[i].m);
tr[i].m=M();
}
}
template<class T>
int bsearch_l(int x,T f){//M=Void
in(x);
for(x+=mx+1;;x>>=1){
if(x&1){
if(f(tr[x-1].d))break;
}
}
for(--x;x<mx;){
x<<=1;
if(f(tr[x+1].d))++x;
}
x-=mx;
return x+1;
}
template<class T>
int bsearch_r(int x,T f){//M=Void
in(x);
for(x+=mx-1;;x>>=1){
if(~x&1){
if(f(tr[x+1].d))break;
}
}
for(++x;x<mx;){
x<<=1;
if(!f(tr[x].d))++x;
}
x-=mx;
return x-1;
}
template<class T>
int find_lm(T f){
int x=1;
while(x<mx){
dn(x);
x<<=1;
if(!f(tr[x].d))++x;
}
x-=mx;
return x;
}
};
template<class T>
struct BIT{
T *a;
int n;
void alloc(int n0){
n=n0;
::alloc(a,n+1);
}
void add(int x,T y){
assert(1<=x&&x<=n);
int _n=n;
for(;x<=_n;x+=x&-x)a[x]+=y;
}
T sum(int x){
assert(0<=x&&x<=n);
T s=0;
for(;x;x-=x&-x)s+=a[x];
return s;
}
void dna(){
Fe(i,1,n)a[i]+=a[i-(i&-i)];
}
T at(int x){
assert(0<=x&&x<=n);
return a[x];
}
void build(){
Fe(i,1,n){
int j=i+(i&-i);
if(j<=n)a[j]+=a[i];
}
}
};
#define CMP(T,x) bool operator<(const T &w)const{return x<w.x;}
#define CMPL(T,x) [](const T &a,const T &b)->bool{return a.x<b.x;}
#define KEYL(T,x) [](const T &a){return a.x;}
template<class T,class F>
void rsort(T *d0,T *d1,int n,int v,F key){
static int t[1<<20];
F(i,0,v)t[i]=0;
F(i,0,n)++t[key(d0[i])];
int s=0;
F(i,0,v){
int a=t[i];
t[i]=s;
s+=a;
}
F(i,0,n)d1[t[key(d0[i])]++]=d0[i];
}
template<class T,class F>
void rsort2(T *d0,int n,F key){
alloc_scope;
T *d1;
alloc(d1,n,0);
rsort(d0,d1,n,2048,[key](const T &x){return key(x)&2047;});
rsort(d1,d0,n,2048,[key](const T &x){return key(x)>>11;});
}
using std::max;
using std::min;
const int inf=1e9;
struct Pos{
int x,y;
}ps[N],ds[N],ps0[N];
bool in(int x,int l,int r){return l<=x&&x<=r;}
struct XY{
int x,y;
XY(int x0=0,int y0=inf):x(x0),y(y0){}
};
XY operator+(XY a,XY b){
return a.y<b.y?a:b;
}
MSegTree<XY> xyt;
BIT<int> xs0,ys0;
int cur[N];
int f1(int x1,int x2,int y1,int y2){
if(x1>x2)return 0;
XY xy=xyt.query(x1,x2);
if(xy.y>y2)return 0;
int id=cur[xy.x]++;
xy.y=(ps0[id].x==ps0[id+1].x?ps0[id+1].y:inf);
xyt.update(xy.x,xy);
return id;
}
template<class T>
struct Sum{
T x;
Sum(T x0=0):x(x0){}
operator T(){return x;}
friend Sum operator+(Sum a,Sum b){return Sum(a.x+b.x);}
};
MSegTree<Sum<int>> xs,ys;
int sumclr(MSegTree<Sum<int>> &ws,int l,int r){
if(l>r)return 0;
int s0=ws.query(l,r);
int s=s0;
while(s0){
int x=ws.bsearch_r(l,[](Sum<int> d){return d.x;})+1;
s0-=ws[x];
ws.add(x,-ws[x]);
l=x+1;
}
return s;
}
struct Q{
int x,y,id;
}qs[N];
int qp=0;
int ans[N];
struct MinI{
int x;
MinI(int x0=inf):x(x0){}
};
MinI operator+(MinI a,MinI b){return MinI(min(a.x,b.x));}
MSegTree<MinI> domt;
int main(){
int n=read(1,maxn);
int m=read(1,maxm);
bool REV=0;
Fe(i,1,n){
ps[i].x=read(1,n);
ps[i].y=read(1,n);
if(REV)std::swap(ps[i].x,ps[i].y);
}
int n0=n;
xs0.alloc(n);
ys0.alloc(n);
Fe(i,1,n){
++xs0.a[ps[i].x];
++ys0.a[ps[i].y];
ps0[i]=ps[i];
}
xs0.build();
ys0.build();
rsort2(ps0+1,n,KEYL(Pos,y));
rsort2(ps0+1,n,KEYL(Pos,x));
xyt.alloc(n);
Fe(i,1,n){
Pos &p=ps0[i];
if(p.x!=ps0[i-1].x){
xyt[p.x]=XY(p.x,p.y);
cur[p.x]=i;
}
}
xyt.range_update(1,n);
xs.alloc(n);
ys.alloc(n);
domt.alloc(n+2);
domt[1]=1;
domt[n+2]=1;
domt.range_update(1,n+2);
Fe(qi,1,m){
int o=read(1,2);
int x=read(1,n),y=read(1,n);
int qx=read(1,n),qy=read(1,n);
if(REV){
o=3-o;
std::swap(x,y);
std::swap(qx,qy);
}
int mx=x+(o==1),my=y+(o==2);
int dp=0;
for(;;){
int i=domt.find_lm([my](MinI d){return d.x<=my;});
if(i>mx)break;
ds[++dp]={i,domt[i].x};
domt.update(i,inf);
}
if(dp){
int x0=ds[1].x,y0=ds[dp].y;
ds[0].y=my;
ds[dp+1].x=mx;
Fe(i,1,dp){
int x1=ds[i].x,x2=ds[i+1].x-1;
int y1=ds[i].y,y2=my-1,y3=ds[i-1].y-1;
if(o==1&&x1<=x2){
int s=sumclr(ys,y1,y3);
if(s)xs.add(x1,s);
}
if(o==2&&y1<=y3){
int s=sumclr(xs,x1,x2);
if(s)ys.add(y1,s);
}
for(;;){
int id=f1(x1,x2,y1,y2);
if(!id)break;
Pos &p=ps0[id];
if(o==1)xs.add(p.x,1);
else ys.add(p.y,1);
--n0;
xs0.add(p.x,-1);
ys0.add(p.y,-1);
}
}
if(x0<mx||x0==mx&&y0==my){
domt.update(x0,my);
}
if(y0<my){
domt.update(mx,y0);
}
}
int y0=domt.query_prefix(qx).x;
int ans0=0;
if(y0<=qy){
int x0=domt.find_lm([qy](MinI d){return d.x<=qy;});
qs[qp++]={qx+1,qy+1,qi};
ans0+=n;
ans0-=n0-xs0.sum(qx);
ans0-=n0-ys0.sum(qy);
ans0-=xs.query().x-xs.query(x0,qx).x;
ans0-=ys.query().x-ys.query(y0,qy).x;
ans[qi]=ans0;
}
}
rsort2(qs,qp,KEYL(Q,x));
BIT<int> bit;
bit.alloc(n+1);
int pp=n;
Fer(i,qp-1,0){
Q &q=qs[i];
for(;pp&&ps0[pp].x>=q.x;--pp)bit.add(n+1-ps0[pp].y,1);
ans[q.id]+=bit.sum(n+1-q.y);
}
Fe(i,1,m)write(ans[i],'\n');
return 0;
}
详细
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 26164kb
input:
995 996 950 481 376 18 141 776 711 966 130 727 468 529 47 39 857 563 832 821 776 472 154 914 825 279 332 415 470 361 968 440 45 560 299 755 703 785 744 387 547 382 3 549 344 573 778 424 784 765 280 115 251 434 695 98 463 506 379 38 610 486 305 623 703 244 856 365 117 360 772 847 331 723 663 991 900 ...
output:
423 473 758 313 694 232 333 784 821 154 247 244 504 54 200 370 872 782 734 174 660 467 76 754 77 3 144 974 526 415 439 694 507 577 258 120 243 3 2 319 313 498 218 828 433 623 981 700 120 55 70 499 375 283 387 128 317 139 220 410 22 547 3 385 430 168 32 0 178 625 677 561 488 672 577 64 144 537 235 54...
result:
ok 996 numbers
Test #2:
score: 0
Accepted
time: 4ms
memory: 28196kb
input:
1000 998 483 753 603 464 306 515 71 717 536 195 335 816 275 223 236 392 764 856 434 203 910 542 595 408 185 212 559 836 27 238 959 252 830 212 946 431 794 63 164 800 566 307 861 840 555 580 37 225 976 897 946 891 459 163 101 679 511 141 628 271 115 202 6 911 131 99 991 975 578 60 193 889 683 437 408...
output:
411 275 9 632 553 5 873 494 172 893 41 194 638 599 747 37 653 919 560 334 536 26 244 448 800 189 64 383 829 662 4 196 785 548 215 430 258 463 132 488 581 217 229 513 765 817 750 3 213 1 624 545 499 79 59 873 211 334 709 371 597 290 0 957 689 192 119 6 322 390 129 464 24 278 876 824 243 663 443 84 61...
result:
ok 998 numbers
Test #3:
score: 0
Accepted
time: 5ms
memory: 30260kb
input:
1000 995 301 895 261 325 211 404 100 381 849 291 851 65 272 465 786 647 26 15 779 368 356 74 26 196 308 809 532 229 643 707 426 380 152 371 622 652 905 793 847 322 574 197 117 960 339 751 246 87 322 948 511 800 967 25 36 906 278 611 586 991 392 314 933 644 42 569 948 769 982 134 518 314 741 491 800 ...
output:
423 240 474 705 507 222 71 715 306 761 254 570 660 638 797 511 581 691 577 876 695 607 230 812 266 89 79 690 456 514 337 549 916 430 79 563 524 372 690 388 853 54 923 388 850 142 307 460 416 605 263 68 928 644 607 911 471 599 455 620 151 2 748 305 88 282 993 59 574 381 568 238 340 644 566 747 0 119 ...
result:
ok 995 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 26160kb
input:
995 997 185 576 420 830 106 145 449 735 293 805 945 57 638 163 316 69 389 66 859 807 632 451 99 437 512 805 645 345 477 93 380 167 502 493 645 333 395 337 729 294 195 209 78 130 592 217 296 864 274 766 791 84 426 303 800 473 198 693 194 756 383 178 404 496 147 487 944 650 316 250 466 523 433 591 794...
output:
67 19 382 84 402 398 880 170 289 60 32 151 17 153 273 203 35 953 2 218 820 458 8 131 80 176 133 487 374 136 756 724 422 128 731 0 685 108 153 24 115 104 646 47 940 854 38 373 831 622 140 49 302 503 460 93 341 105 97 185 228 756 114 466 212 671 967 290 492 859 176 515 249 519 170 0 758 334 899 516 87...
result:
ok 997 numbers
Test #5:
score: 0
Accepted
time: 4ms
memory: 26144kb
input:
996 995 359 306 463 864 932 861 257 565 951 362 874 446 709 578 155 792 887 792 955 630 323 951 273 186 274 877 23 243 643 465 990 822 435 852 403 515 248 410 523 106 512 405 890 889 617 782 539 889 322 419 443 573 805 375 702 60 749 808 147 302 614 933 968 565 681 344 687 665 762 603 17 646 188 34 ...
output:
136 742 755 119 569 60 718 478 674 77 676 593 64 132 6 43 797 750 603 229 693 791 874 899 149 61 417 609 132 243 752 409 504 165 901 647 105 175 743 569 468 877 526 0 52 217 792 190 421 343 457 0 696 29 408 40 0 725 467 11 357 402 545 129 761 512 369 573 428 57 5 912 103 876 64 85 257 386 742 760 67...
result:
ok 995 numbers
Test #6:
score: 0
Accepted
time: 4ms
memory: 26168kb
input:
1000 1000 863 244 541 217 420 994 514 373 675 10 137 518 258 267 691 946 517 233 522 726 468 850 698 633 677 591 651 270 739 673 119 385 213 71 2 177 480 66 398 68 233 965 808 316 883 346 486 966 116 926 850 663 129 22 665 370 6 911 38 919 124 555 236 350 12 98 261 510 124 565 294 447 703 338 408 37...
output:
876 833 394 566 775 762 88 202 176 781 306 2 948 563 855 224 953 842 506 326 857 786 428 443 707 975 120 165 67 93 750 775 412 446 850 777 563 399 922 305 169 556 60 12 122 349 935 363 826 415 94 94 221 668 997 779 0 15 355 824 978 12 772 916 365 21 462 487 87 641 9 871 488 586 813 861 791 30 270 12...
result:
ok 1000 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 26184kb
input:
998 995 968 598 292 481 163 318 24 536 222 338 486 556 600 574 730 474 653 981 669 378 513 79 766 774 100 543 895 535 752 93 883 427 338 874 253 536 235 384 761 822 790 235 823 909 598 348 319 746 650 219 710 485 862 816 847 978 397 497 108 894 61 939 860 633 545 743 130 362 782 855 72 965 906 146 5...
output:
885 513 845 589 139 453 34 725 407 679 629 662 345 547 303 609 463 207 585 227 290 350 105 382 270 19 380 707 413 366 491 284 784 887 642 672 547 651 126 16 26 771 752 723 315 244 66 626 169 923 720 449 889 812 406 53 745 218 151 583 551 520 286 668 626 316 892 937 339 804 7 149 470 32 723 753 341 2...
result:
ok 995 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 26164kb
input:
1000 1000 118 698 770 781 232 191 699 983 873 604 753 289 556 223 577 705 614 711 50 822 59 41 169 346 535 785 956 299 570 831 933 382 193 64 943 608 973 38 283 425 679 272 769 954 369 484 202 454 916 768 474 703 502 751 453 156 202 791 864 285 834 371 631 580 131 132 724 408 789 344 735 982 835 826...
output:
35 241 333 424 60 661 739 244 78 185 303 353 72 756 112 94 0 756 518 941 931 1 217 908 332 211 432 64 930 747 716 474 313 510 827 362 773 257 632 490 417 710 273 179 453 466 473 718 230 714 491 703 74 108 484 40 220 214 0 170 843 121 182 538 606 662 824 0 666 425 620 75 182 16 389 422 0 343 365 299 ...
result:
ok 1000 numbers
Subtask #2:
score: 20
Accepted
Test #9:
score: 20
Accepted
time: 534ms
memory: 93924kb
input:
999996 999996 921339 140126 955508 363759 958698 342406 280137 955674 907511 75721 189876 946586 152058 168837 541857 557702 84498 865987 185574 809224 704828 701026 815379 548000 989515 518951 335439 336866 745570 790616 766723 212893 926629 859003 51261 40866 592510 556235 324926 700261 320946 798...
output:
0 0 953730 0 0 512663 0 0 0 0 407467 0 0 0 0 420 0 0 0 0 0 0 513245 0 0 0 0 0 0 0 0 0 0 0 11756 0 0 7822 0 0 0 0 22726 0 0 0 8233 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13818 349438 0 0 0 0 0 0 6803 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8602 0 0 0 0 0 0 0 15717 0 0 0 0 0 0 0 0 0 0...
result:
ok 999996 numbers
Test #10:
score: 0
Accepted
time: 528ms
memory: 91932kb
input:
999999 999998 593840 81071 226822 360556 984658 495723 774168 212723 961202 460976 425364 312068 135686 76747 312878 654073 77701 260718 263549 822714 513429 976716 926207 374094 338002 624578 897648 332005 630931 241967 134312 551284 743455 355739 997122 435568 642662 63663 795243 94444 696789 3776...
output:
491984 0 125735 422908 0 226183 0 0 0 2158 0 0 280064 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19502 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 747 0 0 0 0 0 0 0 0 0 0 0 0 59265 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 999998 numbers
Test #11:
score: 0
Accepted
time: 509ms
memory: 91972kb
input:
1000000 1000000 883777 318082 13863 878428 601471 340063 593065 648191 228224 432858 585884 205059 770071 963599 897140 940808 68907 32537 396365 642545 822913 211348 629556 82339 190410 157689 907562 173596 271125 337580 145399 606492 749603 897091 193876 205903 678121 530830 947890 589055 721497 7...
output:
261157 0 0 52244 0 0 0 0 4610 0 20801 505827 0 0 0 655799 0 0 0 0 0 163473 0 0 113182 0 0 556199 0 0 0 282902 197726 0 0 0 521870 0 0 0 0 0 0 0 0 0 0 146288 0 136329 0 0 0 0 0 91372 0 0 0 0 0 522077 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 181410 0 0 0 0 0 0 ...
result:
ok 1000000 numbers
Test #12:
score: 0
Accepted
time: 512ms
memory: 93888kb
input:
999999 999998 510701 119376 730813 348187 969509 347009 150616 323014 602592 62582 356110 705851 244692 610953 398605 700401 220533 880308 10280 261179 57162 967936 642021 39765 410482 274103 869979 489138 673553 368275 889697 840948 383673 63696 607963 107808 875626 9630 793170 959823 798227 760130...
output:
65013 21415 692431 0 388141 0 0 0 0 0 0 0 0 0 0 42859 0 0 0 0 0 0 0 0 0 0 8862 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 172112 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1215 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6288 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 999998 numbers
Test #13:
score: 0
Accepted
time: 504ms
memory: 95980kb
input:
999995 999997 148480 214663 902145 539206 771718 173309 708903 967479 984809 352800 21198 668703 879442 719279 593199 82759 286519 788269 873747 641026 246815 368469 585243 532758 177189 437376 566499 996874 663718 794807 847945 784546 68802 611025 636042 793005 656312 200282 90301 316758 516692 913...
output:
408393 0 0 210017 0 0 0 0 0 0 0 0 0 0 0 0 0 0 34271 0 0 0 0 0 0 0 0 0 0 31774 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 624290 27190 0 0 0 0 0 0 0 0 2486 0 0 0 0 0 0 0 0 0 844 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10393 0 0 0 0 0 0 0 0 0 0 0 0 49019 0 0 0 19256 0 0 0 0 0 0 62458 0 0 0 0 0 0 ...
result:
ok 999997 numbers
Test #14:
score: 0
Accepted
time: 525ms
memory: 95976kb
input:
999997 999999 21022 22383 798350 250307 186761 593014 213847 210545 769838 227750 113146 776982 163493 384752 89954 142451 392976 865128 131868 401967 725617 848954 553332 555884 864058 712711 390463 443782 552326 132864 92265 612350 758766 28175 452611 460112 344799 865045 46279 695425 971996 40084...
output:
418555 110151 3026 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33746 0 0 0 0 63321 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60309 0 0 0 0 0 0 6997 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3366 0 0 0 0 0 0 0 0 0 2...
result:
ok 999999 numbers
Test #15:
score: 0
Accepted
time: 531ms
memory: 95812kb
input:
1000000 1000000 151138 713282 47031 196016 951306 826897 695178 570874 853734 782231 254275 640338 166145 420223 154398 814676 670384 826624 992734 757955 486563 187117 169107 198294 973559 847637 993679 950871 217983 940481 10443 754197 627178 253860 607235 514653 806520 269962 714084 706285 32303 ...
output:
493206 119482 243747 3831 0 30734 45299 0 84535 0 0 32866 0 0 0 0 0 0 663462 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 89699 0 76885 0 0 0 0 0 0 0 1347 0 0 0 114007 0 0 822812 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8470 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 518 0 0 946947 0 0 0 0 ...
result:
ok 1000000 numbers
Test #16:
score: 0
Accepted
time: 502ms
memory: 91880kb
input:
1000000 1000000 527391 935776 928283 415193 584695 629231 364709 289656 296798 845590 807666 903716 100319 286344 880595 598376 232292 301072 465491 18715 537421 144321 773917 271368 633706 520802 140917 281422 550382 123883 348051 422164 732339 760403 883443 660056 240883 539950 301009 698713 73859...
output:
956868 480655 0 0 3595 0 0 234921 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4511 0 0 0 975 446781 0 0 0 1210 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 897203 8983 0 0 0 0 0 0 0 0 0 0 0 0 953761 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000000 numbers
Subtask #3:
score: 20
Accepted
Test #17:
score: 20
Accepted
time: 1343ms
memory: 105436kb
input:
999995 999997 261379 334440 985281 986034 549380 718157 670003 253925 533027 437989 326806 983213 965935 756259 229069 686789 331338 684961 957559 390618 937820 959719 338153 779814 582581 965418 634156 421264 308778 938878 913059 390904 481477 431492 739774 793015 901442 934600 256704 991485 366691...
output:
160635 633543 123519 313576 450015 383636 574186 2373 203701 326075 117994 567275 652824 199778 380317 380374 105875 373857 788346 703176 609801 648161 367059 497975 57979 478851 745054 75935 543062 251837 769828 436489 480966 235835 509625 757188 763486 396842 262680 2240 267171 165787 558963 16523...
result:
ok 999997 numbers
Test #18:
score: 0
Accepted
time: 1063ms
memory: 109868kb
input:
999995 1000000 503105 994319 301845 645636 538613 176453 944222 13642 220616 61270 445661 771824 758217 940994 11782 103262 159910 298805 317312 333018 741333 381578 579921 219986 605953 400913 625208 245340 729891 669648 186684 920562 118589 936228 281749 70955 103542 8281 854584 972667 663720 1425...
output:
8906 95485 8020 794529 288722 194571 738405 141163 47184 574675 21317 361918 336935 752285 747548 767325 485498 549919 836009 224230 243311 43089 166877 861403 1740 800031 757202 757248 571568 258896 110506 308599 111448 82706 495681 126271 557664 498332 507141 161535 251016 116433 490396 350530 854...
result:
ok 1000000 numbers
Test #19:
score: 0
Accepted
time: 1673ms
memory: 108144kb
input:
999997 1000000 44415 540937 815519 772048 580901 820033 176932 136598 26200 658165 495640 298186 350660 672003 66843 751311 886121 454924 75107 454946 855867 668594 952401 723257 914495 648341 931555 500560 451289 811080 275183 969584 28984 255298 971792 603789 290513 485349 63131 4066 4993 123137 6...
output:
629719 695599 351561 83909 248197 337451 198910 119007 163901 59655 227999 446205 417989 21251 943060 809056 530827 874242 191820 190031 801897 103766 56477 114351 865146 677995 221128 278416 622213 580214 223576 311442 602474 22418 10224 852728 546723 793775 936547 18769 695901 400642 163668 131209...
result:
ok 1000000 numbers
Test #20:
score: 0
Accepted
time: 1621ms
memory: 108436kb
input:
999995 999995 583944 643022 937405 396314 664613 53634 851937 959727 682251 262542 332058 495766 657697 254050 368945 648181 175500 409923 987447 663924 254362 212955 27186 48916 280933 263728 376404 531873 991175 304206 637107 818051 718055 603621 219979 376988 818262 602594 182634 716446 199549 42...
output:
632589 674038 421313 484901 850231 228438 726812 388070 754679 535180 282906 25258 23979 984419 946557 113528 158768 603008 400873 344667 550891 469199 301296 257606 310724 113289 667078 869781 273972 414507 36966 141760 266471 765423 406244 590218 968606 19385 46201 1519 39710 219752 427711 92415 6...
result:
ok 999995 numbers
Test #21:
score: 0
Accepted
time: 1351ms
memory: 107744kb
input:
1000000 1000000 447619 721571 584229 399494 614240 965088 204795 826646 448424 16919 866545 997174 657300 767860 490299 320401 773237 573187 494243 285955 630714 533001 811444 822428 571608 72868 490258 309897 415722 410945 967983 117451 928078 616204 939548 894410 622192 510197 568931 946541 594774...
output:
126935 145263 465828 476012 65533 42535 698958 492977 890460 175334 194482 579490 712753 695360 739259 853109 150308 228326 104307 750668 105724 512722 81223 925835 382011 92740 184439 918760 104781 443444 190528 204480 31387 835933 934756 66557 530040 18748 381135 735303 30969 306423 125340 33784 7...
result:
ok 1000000 numbers
Test #22:
score: 0
Accepted
time: 1619ms
memory: 106968kb
input:
1000000 1000000 563011 69168 799795 322619 625047 265910 302908 329651 912744 87238 944646 651913 883129 540212 154443 308737 809426 72823 394629 784304 722788 621382 600870 838097 351383 148859 863544 219752 279356 573627 168233 338737 748815 773018 779663 11919 819024 722313 784467 172146 429478 8...
output:
931763 507651 2891 279771 232600 358080 668537 179794 209284 323888 8579 28498 724380 790693 913562 742416 237268 811986 666427 110749 337341 45733 893515 541297 415398 387692 840824 806569 300977 7251 210484 844863 141462 768680 694505 368468 120097 826126 58764 335812 638189 244154 574681 705704 4...
result:
ok 1000000 numbers
Test #23:
score: 0
Accepted
time: 1675ms
memory: 107764kb
input:
999999 999998 549904 780695 952102 832337 321082 698470 315767 459429 88631 296205 224845 246509 898700 395777 277973 403130 437048 186188 393884 45421 993904 511710 94564 534733 606016 40744 294330 813572 957779 147335 315712 805921 835751 978801 764915 214826 33564 855982 174621 309776 202372 4386...
output:
174929 683585 23870 145186 591016 146066 527528 825193 571238 633087 677612 57791 250466 20273 94886 182538 544573 426519 148353 8778 283430 226442 23493 85639 27407 955906 174708 192446 139541 672132 487223 351873 370386 161299 345077 163475 831109 778917 16063 732 359442 2254 570035 292433 527730 ...
result:
ok 999998 numbers
Test #24:
score: 0
Accepted
time: 1587ms
memory: 108540kb
input:
1000000 1000000 875926 620802 927410 582189 453297 27134 625927 194770 285863 198107 758448 934846 628394 508725 472741 244210 63544 906210 694594 426018 95086 100899 791006 237438 459186 660344 422538 932319 786905 189449 38062 851236 615341 58794 935296 669950 41835 430485 638425 532888 887360 956...
output:
314353 240231 222662 88736 363994 50619 459541 704120 315257 144316 755815 369269 315280 552329 382758 939953 104281 715086 891561 724596 298843 885639 44610 110591 551022 693346 436359 15173 17290 155448 18605 889862 815068 470390 238390 874503 68546 21916 704446 344934 357808 355718 103549 888118 ...
result:
ok 1000000 numbers
Subtask #4:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #25:
score: 20
Accepted
time: 385ms
memory: 57260kb
input:
300000 300000 189563 143721 113019 232012 283009 152341 235960 146797 105782 100287 206719 212533 238247 192897 161513 101004 277069 129851 143907 67623 222005 158357 160618 31368 104158 90114 148304 15002 40521 169190 123876 140598 98925 113096 140488 204997 261142 106636 248565 219481 169567 27352...
output:
133975 58943 108003 271435 240472 18520 37226 64824 110443 24926 100107 57084 94462 77185 184644 44920 9569 36924 35679 185190 185985 59207 158326 295411 139708 12926 12708 66759 205320 8991 58151 18350 77099 21936 68243 193824 3369 33845 198412 152705 74697 80791 17996 195006 131057 125867 119782 4...
result:
ok 300000 numbers
Test #26:
score: 0
Accepted
time: 288ms
memory: 56360kb
input:
299996 299995 79019 129698 234860 13102 158780 130519 261477 120960 60568 211885 256377 296230 147012 276380 185086 180605 204971 176492 88129 293796 227141 23984 220343 191736 58992 215794 109290 47137 212346 145295 153762 283639 47157 61831 123097 99924 192275 67142 245853 133217 66762 222393 1151...
output:
131818 260140 3505 105184 9284 13024 251956 148517 174364 116271 35508 244852 118953 118474 103947 120727 281820 252822 180298 79580 281785 12209 210581 252212 1720 26573 27339 9033 43182 93870 263052 28232 20251 213930 3831 16733 47322 1601 11575 1448 196631 18062 199534 253177 147386 27733 84098 1...
result:
ok 299995 numbers
Test #27:
score: 0
Accepted
time: 457ms
memory: 57948kb
input:
299995 299996 188804 55811 167434 153058 154932 74503 173622 52433 26915 214178 234016 135998 15896 265764 8622 97137 227795 200595 48807 86677 33673 153470 152556 137563 266890 148077 94382 46942 282125 163817 268632 4779 234991 130657 187910 159651 79388 104610 233085 133115 150223 76879 54979 261...
output:
19418 250508 142313 50795 202976 270503 29304 38129 149746 192581 190066 194819 196136 137213 96812 14034 229385 45437 163195 236623 128107 160769 243153 98499 277308 250726 46463 246021 26467 77438 244641 158038 98826 2702 13513 127549 178416 26046 33066 57526 49752 126683 237234 111752 200579 2880...
result:
ok 299996 numbers
Test #28:
score: 0
Accepted
time: 480ms
memory: 57804kb
input:
300000 300000 287600 159144 154753 83801 270907 47305 204449 62527 191095 292913 144320 60580 93307 49515 3998 158033 282445 245654 145947 29326 92088 215104 277974 232931 26354 28648 70712 212065 10723 229150 150470 127263 9535 37547 23636 86990 236638 251737 80546 258533 262007 100054 12817 102109...
output:
247971 230684 161145 23290 227117 78047 82712 45112 32137 62021 38426 157008 60980 192430 120614 32520 155874 263799 127259 224499 38665 221398 7452 166265 51356 271847 31072 159795 233035 67072 107748 83341 22705 974 17753 83155 145154 160389 151396 210838 189311 57161 230585 21207 35195 219190 710...
result:
ok 300000 numbers
Test #29:
score: 0
Accepted
time: 393ms
memory: 56956kb
input:
299996 299998 184207 84911 287984 212458 244826 86388 197096 179170 44973 252282 172396 89784 102544 201463 22457 247915 95428 192248 85330 147275 156957 163186 54903 157709 28992 129096 163944 169142 292808 198914 1336 127387 119305 47621 148571 183483 209901 108145 251623 284161 183206 100059 1405...
output:
26149 69871 215541 1914 9018 90038 175590 120535 18222 162774 164013 118400 158442 97990 63361 175299 260728 55139 6618 3969 84166 196689 54864 39135 99707 227834 218578 214866 52660 241197 146719 21361 221940 27645 111387 19507 32703 133617 78042 283204 199994 75334 225998 287307 157383 20181 25588...
result:
ok 299998 numbers
Test #30:
score: 0
Accepted
time: 487ms
memory: 57132kb
input:
299996 299999 77650 14898 64549 295007 73990 219923 119584 280074 11286 11441 272839 28325 123199 3684 61093 88515 289951 214024 173865 243628 4479 136903 57898 46525 255260 212810 55907 23912 22768 241324 278290 242498 198303 64731 244399 7499 25694 122349 168625 247625 299288 255534 216462 140161 ...
output:
143226 74062 207551 47856 141644 32608 33152 204761 52682 16602 171109 205983 189016 151648 5046 238148 1748 96002 76006 55690 224514 136312 148838 94901 103801 78863 33410 81183 115448 50915 3242 207678 176913 64793 83278 94525 82130 116737 206916 114406 84673 246977 173449 129299 80085 214230 5954...
result:
ok 299999 numbers
Test #31:
score: 0
Accepted
time: 505ms
memory: 62296kb
input:
299997 299997 190993 215622 243261 26985 127770 251331 111155 41690 101159 31069 29199 285927 140484 139072 135109 18256 146623 239470 158906 119232 241906 281104 263930 235599 80043 130803 265878 266345 77202 175920 289086 99035 140600 133644 169588 266548 230444 163562 94229 242491 56720 190479 18...
output:
290866 14937 13346 240114 4793 217485 129252 11210 189154 44538 249342 87105 250322 101710 188454 24352 131134 86431 82991 12889 232740 38 3237 150432 227843 33074 10172 147166 128156 7611 26151 27472 41580 3212 189958 186596 105636 3452 45187 183054 61073 41651 10288 45726 93600 140880 229014 27814...
result:
ok 299997 numbers
Test #32:
score: 0
Accepted
time: 471ms
memory: 59616kb
input:
300000 300000 148349 245555 245354 71011 149343 269464 242383 282469 148527 292294 42415 86272 13679 134550 212614 282776 233124 41381 146910 183006 137371 184324 224049 137290 234770 86628 228569 46338 218151 69152 24578 220200 106904 39810 264055 196329 13754 17665 288981 124549 259685 40701 28486...
output:
49781 296960 75532 229085 23875 75341 209 195487 138057 129109 154280 11922 15783 83877 223219 209219 113978 167906 175343 11182 71695 137117 241246 136477 110931 67885 4617 194285 128747 128736 260623 257512 62455 40155 14234 128411 137319 239092 46829 270200 39346 145983 59972 237948 2435 94043 17...
result:
ok 300000 numbers
Subtask #5:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #33:
score: 20
Accepted
time: 1615ms
memory: 104360kb
input:
1000000 1000000 527057 870207 62318 386643 246170 135479 15332 814242 853607 819602 661978 135735 727369 794653 239840 417449 193844 180967 670319 953449 121632 133189 285718 675312 847342 857660 911443 348634 406484 665426 619413 738374 973660 487875 897975 628981 95320 336373 986146 440494 3686 94...
output:
502709 4378 804347 507197 656721 683800 211837 352494 334034 28662 284894 44128 243285 625969 740241 116139 511373 481852 748418 625156 761625 259293 240159 800284 689841 759271 13511 562433 702391 862275 797302 227007 851791 39559 701291 648410 647927 14723 523006 307469 47111 238828 556956 36718 7...
result:
ok 1000000 numbers
Test #34:
score: 0
Accepted
time: 1168ms
memory: 109248kb
input:
999995 999995 651426 945699 52015 238214 238275 707060 262561 650406 404029 633378 565481 439014 620894 277882 247543 395877 162004 888838 725881 416730 806616 166296 762831 393381 841471 499284 25217 101250 938073 783236 329564 25932 449295 875959 8096 827567 643696 983358 522425 984422 56637 86636...
output:
9092 207936 425852 757131 799946 376518 81987 754069 760927 81515 222428 575155 609094 310274 149960 341223 28833 239919 138056 741463 537762 156371 295339 226286 722268 820236 109150 641793 441461 727458 128425 7281 328093 229566 464965 489736 790448 341977 683694 507573 82312 67400 766412 307058 4...
result:
ok 999995 numbers
Test #35:
score: 0
Accepted
time: 1992ms
memory: 107844kb
input:
1000000 1000000 915997 131080 726227 905570 841366 651450 538411 316570 604986 331082 952930 434524 143432 872327 381396 912926 720075 172654 955541 78683 13121 624658 220933 747962 674038 56596 816103 280152 270936 857687 796820 942714 568780 58054 570516 983834 985449 315859 376149 566354 232356 1...
output:
205002 585811 69514 283743 81143 241116 491527 167262 550457 814491 120554 3084 263099 175998 606126 778266 560021 305114 357121 981740 68073 70717 841862 299422 398614 300305 848999 695136 842425 164137 488744 711655 422105 583719 508084 243725 782787 339452 285660 512423 946491 137361 328938 22332...
result:
ok 1000000 numbers
Test #36:
score: 0
Accepted
time: 1876ms
memory: 107056kb
input:
1000000 1000000 150739 751391 506983 63096 884932 547035 2190 689660 562566 369233 873150 572658 924949 271881 770661 120112 790737 467963 434143 854238 624749 804346 569889 20896 117601 570456 837159 278806 669038 311912 525719 759763 182541 391445 646745 450607 243052 500140 642649 946911 797653 3...
output:
86310 749420 712668 358213 262607 610624 727300 492258 488830 347620 542739 370304 503994 169728 87698 52948 594469 323656 647722 485956 821313 194329 218795 414885 720267 246810 99153 40160 519238 434421 846392 349741 660148 583392 169704 341771 486638 390630 73339 475144 371420 97007 79077 291446 ...
result:
ok 1000000 numbers
Test #37:
score: 0
Accepted
time: 1568ms
memory: 105536kb
input:
999997 1000000 326813 836438 660095 500957 156840 970405 558934 116262 415858 656797 61423 860041 886954 894983 844315 296372 489459 75158 696873 728051 321072 858285 574682 648919 841402 813600 292157 318327 433981 808970 765509 140622 364840 899777 979697 716247 301865 908019 818981 844271 2829 46...
output:
401172 24036 860078 491660 158642 8316 577291 449545 634397 959599 207750 639137 582792 943488 83395 239020 264293 928111 559684 149714 565564 964707 12763 791158 545697 223052 753693 205382 616198 56582 549540 298422 75005 92838 142070 309100 803704 189959 440612 604506 433574 931608 201374 233945 ...
result:
ok 1000000 numbers
Test #38:
score: 0
Accepted
time: 1887ms
memory: 106736kb
input:
1000000 1000000 601296 665854 297900 102700 693456 741225 493337 109330 292282 982172 347605 277869 439714 759989 285654 111360 140329 379832 154002 938339 464120 219412 436854 420216 242985 143983 980131 297922 852749 134681 338641 20120 793629 794583 891009 325638 183018 716606 847366 717225 28292...
output:
622364 281133 202654 381537 115338 744279 167290 596110 288290 83184 28083 19375 940656 428337 35841 615491 414275 871953 613438 978472 441143 44139 120116 89196 156943 596378 590732 560308 528208 252261 543122 5183 563154 742836 881228 245309 654268 838699 127361 564683 300262 265851 91295 979479 1...
result:
ok 1000000 numbers
Test #39:
score: 0
Accepted
time: 1938ms
memory: 107300kb
input:
999996 999996 664451 986455 234620 98119 901931 987296 481981 347041 434366 439392 634265 146098 374502 770738 660671 539576 289585 639612 394235 416438 694812 976442 218665 927539 423928 379357 995837 23433 311224 428187 827472 356389 220432 451241 987093 174507 904143 3613 653913 307223 275290 223...
output:
724429 56311 461374 712706 911035 119990 274914 429101 139383 118092 48853 429723 145943 770596 274687 828245 476420 452885 903907 335838 47028 729722 661 431679 484553 288376 502744 564718 666632 783048 273878 903608 158530 168182 250804 788371 529557 592531 13671 26483 718098 755560 562307 788883 ...
result:
ok 999996 numbers
Test #40:
score: 0
Accepted
time: 1912ms
memory: 107600kb
input:
1000000 1000000 423538 12107 844589 986915 204379 601010 259635 728575 693823 306312 869741 616130 33447 238212 826190 129937 378701 326026 653161 810500 789874 30196 60365 436695 900410 911414 399765 74105 9128 469233 684448 50577 34763 681794 704502 397391 601963 509690 971052 394111 452656 216032...
output:
153867 391294 280811 717687 897510 107194 924308 910198 144743 642641 356450 590073 296495 512804 719906 127642 551174 275769 280771 148931 197239 652727 5633 35306 969569 389879 447970 840639 459667 228206 207029 960669 31049 377246 665922 548519 236350 284122 781097 412781 756292 397488 186894 528...
result:
ok 1000000 numbers