QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#526650 | #4409. 袜子 | Displace_ | 100 ✓ | 4098ms | 40388kb | C++14 | 7.3kb | 2024-08-21 19:08:14 | 2024-08-21 19:08:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(!isdigit(ch)){if(ch=='-') f^=1;ch=gc();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
}fin,fout;
const int N=50005, M=500005;
inline bool chk(int x1, int y1, int x2, int y2){
bool op=1;
if(x1<0) op^=1;
if(x2<0) op^=1;
if(op) return (ll)y1*x2<(ll)y2*x1;
else return (ll)y1*x2>(ll)y2*x1;
}
inline bool chk2(int x1, int y1, int x2, int y2){
bool op=1;
if(x1<0) op^=1;
if(x2<0) op^=1;
if(op) return (ll)y1*x2<=(ll)y2*x1;
else return (ll)y1*x2>=(ll)y2*x1;
}
int n, m, B;
vector<pii> vec[N];
struct node{
int a, b, c, id;
inline bool operator <(const node &x)const{
return chk(b, -a, x.b, -x.a);
}
}v[M];
int ans[M]; ll out[M];
vector<pii> bin;
struct node2{
int a, b, x, y;
inline bool operator <(const node2 &z)const{
if((ll)a*z.b==(ll)z.a*b){
if(x==z.x) return y<z.y;
return x<z.x;
}
return chk(a, b, z.a, z.b);
}
};
int pos[N], rev[N];
inline void work(int x, int y){
if(pos[x]>pos[y]) return ;
swap(rev[pos[x]], rev[pos[y]]);
swap(pos[x], pos[y]);
}
int tot;
inline void solve(){
sort(bin.begin(), bin.end());
tot=bin.size();
vector<node2> swp;
for(int i=0; i<tot; ++i){
pos[i]=i; rev[i]=i;
for(int j=i+1; j<tot; ++j){
if(bin[i].fi==bin[j].fi) continue;
swp.emplace_back((node2){bin[j].fi-bin[i].fi, bin[j].se-bin[i].se, i, j});
}
}
sort(swp.begin(), swp.end());
int p=0;
for(int i=1; i<=m; ++i){
while(p<(int)swp.size()&&chk2(swp[p].a, swp[p].b, v[i].b, -v[i].a)) work(swp[p].x, swp[p].y), ++p;
if(v[i].b>=0){
int l=0, r=tot-1, res=-1;
while(l<=r){
int mid=(l+r)>>1;
if((ll)bin[rev[mid]].fi*v[i].a+(ll)bin[rev[mid]].se*v[i].b+(ll)v[i].c<0ll) {res=mid, l=mid+1;}
else r=mid-1;
}
ans[v[i].id]+=res+1;
}
else{
int l=0, r=tot-1, res=tot;
while(l<=r){
int mid=(l+r)>>1;
if((ll)bin[rev[mid]].fi*v[i].a+(ll)bin[rev[mid]].se*v[i].b+(ll)v[i].c<0ll) {res=mid, r=mid-1;}
else l=mid+1;
}
ans[v[i].id]+=tot-res;
}
}
}
struct node3{
int a, b, c;
inline bool operator <(const node3 &x)const{
if(a^x.a) return a<x.a;
return b<x.b;
}
};
vector<node3> bin2;
set<int> st[N];
int rk[N], rkk[N];
ll tr[N], trr[N];
inline void mdf(int x, int v){
++x;
for(; x<=tot; x+=(x&-x)) tr[x]+=v;
}
inline ll get(int x){
++x; ll ret=0;
for(; x; x-=(x&-x)) ret+=tr[x];
return ret;
}
inline void mdff(int x, int v){
++x;
for(; x; x-=(x&-x)) trr[x]+=v;
}
inline ll gett(int x){
++x; ll ret=0;
for(; x<=tot; x+=(x&-x)) ret+=trr[x];
return ret;
}
typedef set<int>::iterator IT;
inline void work2(int x, int y){
if(pos[x]>pos[y]) return ;
if(bin2[x].c==bin2[y].c) {
swap(rev[pos[x]], rev[pos[y]]);
swap(pos[x], pos[y]);
return ;
}
IT it=st[bin2[x].c].lower_bound(pos[x]);
int nrk=rk[*it], nrkk=rkk[*it];
int lstrk=rk[*it], lstrkk=rkk[*it];
++it;
while(it!=st[bin2[x].c].end()&&(*it)<pos[y]){
--rk[*it]; mdf(*it, -1); ++nrk;
++rkk[*it]; mdff(*it, 1); --nrkk;
++it;
}
mdf(pos[y], nrk-rk[pos[y]]);
mdff(pos[y], nrkk-rkk[pos[y]]);
st[bin2[x].c].erase(st[bin2[x].c].lower_bound(pos[x]));
st[bin2[x].c].insert(pos[y]);
it=st[bin2[y].c].lower_bound(pos[y]);
int nrk2=rk[*it], nrkk2=rkk[*it]; rk[*it]=nrk; rkk[*it]=nrkk;
if(it!=st[bin2[y].c].begin()) {
--it;
while((*it)>pos[x]){
++rk[*it]; mdf(*it, 1); --nrk2;
--rkk[*it]; mdff(*it, -1); ++nrkk2;
if(it==st[bin2[y].c].begin()) break;
--it;
}
}
mdf(pos[x], nrk2-lstrk); rk[pos[x]]=nrk2;
mdff( pos[x], nrkk2-lstrkk); rkk[pos[x]]=nrkk2;
st[bin2[y].c].erase(st[bin2[y].c].lower_bound(pos[y]));
st[bin2[y].c].insert(pos[x]);
swap(rev[pos[x]], rev[pos[y]]);
swap(pos[x], pos[y]);
}
inline void solve2(){
sort(bin2.begin(), bin2.end());
tot=bin2.size();
vector<node2> swp;
for(int i=0; i<tot; ++i){
pos[i]=i; rev[i]=i; st[bin2[i].c].clear();
for(int j=i+1; j<tot; ++j){
if(bin2[i].a==bin2[j].a) continue;
swp.emplace_back((node2){bin2[j].a-bin2[i].a, bin2[j].b-bin2[i].b, i, j});
}
}
for(int i=1; i<=tot; ++i) tr[i]=trr[i]=0;
for(int i=0; i<tot; ++i){
st[bin2[i].c].insert(i);
rk[i]=st[bin2[i].c].size();
mdf(i, rk[i]);
}
for(int i=tot-1; i>=0; --i){
rkk[i]=st[bin2[i].c].size()+1-rk[i];
mdff(i, rkk[i]);
}
sort(swp.begin(), swp.end());
int p=0;
for(int i=1; i<=m; ++i){
while(p<(int)swp.size()&&chk2(swp[p].a, swp[p].b, v[i].b, -v[i].a)) work2(swp[p].x, swp[p].y), ++p;
if(v[i].b>=0){
int l=0, r=tot-1, res=-1;
while(l<=r){
int mid=(l+r)>>1;
if((ll)bin2[rev[mid]].a*v[i].a+(ll)bin2[rev[mid]].b*v[i].b+v[i].c<0) {res=mid, l=mid+1;}
else r=mid-1;
}
out[v[i].id]+=2ll*get(res); out[v[i].id]-=res+1;
}
else{
int l=0, r=tot-1, res=tot;
while(l<=r){
int mid=(l+r)>>1;
if((ll)bin2[rev[mid]].a*v[i].a+(ll)bin2[rev[mid]].b*v[i].b+v[i].c<0) {res=mid, r=mid-1;}
else l=mid+1;
}
out[v[i].id]+=2ll*gett(res); out[v[i].id]-=tot-res;
}
}
}
int main(){
// freopen("D:\\nya\\acm\\B\\test.in","r",stdin);
// freopen("D:\\nya\\acm\\B\\test2.out","w",stdout);
fin>>n>>m; B=sqrt(m)*0.6;
for(int i=1, x, y, z; i<=n; ++i){
fin>>x>>y>>z;
vec[z].emplace_back(x, y);
}
for(int i=1; i<=m; ++i){
fin>>v[i].a>>v[i].b>>v[i].c; v[i].id=i;
}
sort(v+1, v+m+1);
for(int i=1; i<=n; ++i){
if((int)vec[i].size()>=B){
for(int l=0; l<(int)vec[i].size(); l+=B){
bin.clear();
for(int r=0; r<B&&l+r<(int)vec[i].size(); ++r){
bin.emplace_back(vec[i][l+r]);
}
solve();
}
for(int i=1; i<=m; ++i) {
out[i]+=(ll)ans[i]*ans[i];
ans[i]=0;
}
}
else{
for(auto t:vec[i]) bin2.push_back((node3){t.fi, t.se, i});
if((int)bin2.size()>=B) solve2(), bin2.clear();
}
}
if(bin2.size()) solve2();
for(int i=1; i<=m; ++i) fout<<out[i], fout.pc('\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 3ms
memory: 13912kb
input:
1000 1000 8756 4483 237 -7891 -2818 114 8667 -7202 36 8150 -2 248 -4483 -9934 375 -9669 -1815 802 4008 9788 22 -2193 -4988 307 -9813 -4926 22 6344 8542 93 -9906 -9906 38 -3791 -2822 814 -7118 8408 51 -779 9589 3 -3211 1342 73 2346 -6502 112 31 -5037 6 3714 -4554 118 8788 6735 533 3860 -4232 5 3257 6...
output:
1047 1034 1001 1061 1060 956 1029 1001 1048 1001 1052 1023 1077 0 1077 1015 1060 1012 1022 1022 1077 1369 993 1001 1060 1003 1077 1034 1063 0 1001 1038 0 1001 1077 1001 1063 1063 1060 1034 0 1060 1060 1077 1031 1021 939 1023 849 1001 1060 1000 1008 1150 1007 878 1060 1060 1020 1043 1045 1077 1048 0 ...
result:
ok 1000 numbers
Test #2:
score: 5
Accepted
time: 0ms
memory: 15896kb
input:
1000 1000 -809378 594895 7 -463965 286585 108 492337 -110361 235 163858 -391125 15 -546105 -878318 214 360416 -730538 407 -298417 -177165 227 752631 -788118 51 17699 323971 105 843170 208717 105 766811 396573 69 127415 309072 39 637608 -188063 352 224425 -952868 139 850507 751278 110 -995626 648647 ...
output:
997 969 935 993 9 1023 998 1014 999 969 1001 982 1023 937 1028 1035 973 1029 953 969 25 1001 889 976 985 1023 937 1023 1006 992 937 1009 1023 969 969 1001 925 937 969 1001 969 1023 937 937 1000 1023 969 932 962 1001 969 994 937 1001 937 905 1008 937 1023 958 1023 1001 731 1015 956 988 945 970 1042 9...
result:
ok 1000 numbers
Test #3:
score: 5
Accepted
time: 3ms
memory: 17988kb
input:
1000 1000 -329387625 -341019218 102 13965986 806087844 9 -528171131 227425809 15 786487633 15830440 3 539535861 -963497336 7 -742845817 -372626578 35 -787231340 -132749801 3 -543467667 -942295910 119 -672244153 -833463748 15 -641088972 317851104 1 65665573 -823079703 26 247807062 -882007619 11 -6610...
output:
4529 5025 4868 4426 3446 3771 3781 3700 4842 4604 4259 3557 3731 3538 3979 4367 4879 3595 4336 3446 4754 3632 3762 3750 3446 4879 4728 4668 4610 3781 4816 3600 3760 4868 3760 3446 4387 3446 3760 4529 4447 4019 4879 3781 3611 4529 4529 4865 4711 3446 4868 4104 3446 3760 3781 3387 4647 4736 4519 3730 ...
result:
ok 1000 numbers
Test #4:
score: 5
Accepted
time: 0ms
memory: 16072kb
input:
1000 1000 -240930145 126765047 4 5029224 -538225798 8 748056353 -6881636 1 254300626 659262809 8 590237623 -34857701 1 655683714 -171537454 3 582680000 -835569740 4 -746501072 381914331 1 -696675178 165921148 6 73362513 -665223969 4 -204185218 875019442 5 -656420293 -589534031 5 -326306612 -57437624...
output:
23040 20550 23040 23667 19699 22762 21160 20433 22290 21231 20550 21874 20500 20550 23040 22949 23485 24394 21591 24045 19681 20491 21324 22226 20082 24060 20505 23603 19699 20550 21488 23667 20491 19699 23667 21061 21600 20550 21015 21876 22917 22481 23040 22902 19699 20858 19699 21919 21725 20490 ...
result:
ok 1000 numbers
Test #5:
score: 5
Accepted
time: 0ms
memory: 14712kb
input:
1000 1000 -886939246 -956433905 4 458364194 -989591596 1 -69057070 -647489199 2 -34535206 -500686466 1 671489436 -224022957 1 -487072455 294047705 4 -284801195 490213612 1 27112031 -736294945 1 -408100248 967227200 4 107685527 147821041 1 -759670783 -778138619 7 554606387 -117974098 2 -543318085 -66...
output:
126533 125819 126518 116416 115569 112523 113786 120221 115569 126703 126174 125954 113560 113560 115569 129937 124149 120150 115569 120801 119337 129285 126174 126174 127311 119240 120252 127733 124149 113560 113560 115569 115936 130657 120313 120798 115569 131931 112735 120197 123145 115569 120234...
result:
ok 1000 numbers
Test #6:
score: 5
Accepted
time: 3ms
memory: 13992kb
input:
1000 1000 -140707073 -709357437 276 666979616 294563099 34 507506113 -978340110 245 -41619729 -632363033 28 450190358 -768866476 86 -106476442 -83684337 574 477466216 479545563 220 196637637 -181541675 119 427079800 435777395 406 30465211 86113444 760 129968522 814179371 129 719311691 325225596 48 -...
output:
1003 986 1063 1104 1058 1054 1004 1018 1011 1082 1065 1009 967 1081 1071 964 1014 964 1015 1030 1010 1059 1019 1027 1062 1027 1006 1064 1081 1027 1086 1037 1015 995 1081 1000 1015 1056 1014 1005 966 1024 1095 1003 1012 993 1081 1003 1058 1027 1039 1015 1045 1014 967 1003 1014 959 1047 1006 1014 1082...
result:
ok 1000 numbers
Test #7:
score: 5
Accepted
time: 6ms
memory: 13872kb
input:
1000 1000 -447447700 -591263241 63 -216023636 -506993336 886 -723265777 481650149 2 380816011 -971341762 11 -433458798 217059466 113 -649457481 318097209 59 998475552 -512422664 128 -293129715 -964655164 511 -403596696 -668671938 515 -212213731 -448158397 80 -761541201 -739537496 122 -686289475 -803...
output:
914 914 940 960 991 1045 1051 1053 1029 1015 914 1092 961 1051 958 988 1032 1051 1092 961 961 946 1051 1037 961 986 1023 1009 1051 1057 1044 1092 1025 1092 956 914 980 1087 927 1092 1005 1006 969 999 1002 914 914 1041 932 1031 1056 1048 1058 1070 1027 1092 1057 964 1051 961 1051 1064 1062 914 971 10...
result:
ok 1000 numbers
Test #8:
score: 5
Accepted
time: 3ms
memory: 16420kb
input:
1000 1000 -541722175 476510525 31 628338000 759271580 381 -271238678 800070438 512 780664157 -680638999 186 -426546737 121982760 93 270959547 -103484346 577 -598325723 -197010965 114 112923702 786079875 121 -519492810 -842104927 16 555941748 784488471 103 -689093484 169597790 85 -164649986 -99979169...
output:
1004 885 1009 950 994 1095 1008 1071 1016 862 958 1009 1095 1054 1007 1007 1095 1007 1082 1095 1095 885 890 1009 913 1042 987 885 885 1071 886 1065 1009 1007 1005 1121 888 1033 918 1074 1051 1042 885 1008 1004 1009 1095 1095 1007 1102 1052 1028 1089 1095 905 890 1027 1095 1095 1129 1007 885 1029 103...
result:
ok 1000 numbers
Test #9:
score: 5
Accepted
time: 6ms
memory: 14196kb
input:
1000 1000 223130280 -358540334 70 -446423718 -649264507 25 952545239 -115890499 74 198701646 411091447 52 -543555719 -183987016 671 -138533088 462438454 72 780376261 275581957 624 -269723997 -448427286 73 706578440 987790609 157 -804222735 801819299 503 915059774 569425246 54 -221158650 -190676516 2...
output:
1022 1010 1032 1085 978 1022 927 948 1032 1081 1030 948 1018 980 965 936 1022 1010 1010 1016 942 1030 1030 948 1022 950 1010 1022 1032 948 937 960 1011 1010 1010 1022 1067 1010 1095 1017 980 1070 948 1019 964 1045 1022 1069 1029 1086 1022 1010 948 1010 984 944 1010 1010 949 1030 985 957 943 1028 107...
result:
ok 1000 numbers
Test #10:
score: 5
Accepted
time: 3ms
memory: 16736kb
input:
1000 1000 -580044540 7764137 285 -849966519 -358165808 235 877921194 265967662 564 304785558 62822807 48 116178894 720156161 210 894895305 -213358952 51 655074511 -309026876 195 296310508 -237014578 134 -255019899 626409905 55 -557361321 990535673 287 106143372 -769370053 523 -935285432 -394592511 8...
output:
887 862 1006 824 927 883 1017 1020 1010 909 1022 1006 942 855 1051 912 885 876 873 862 1032 892 883 1032 909 1007 912 862 841 876 1010 1033 912 883 985 862 1006 912 930 912 985 1021 934 1006 808 873 1034 1006 1032 912 862 1030 1000 880 1009 824 1032 894 1092 873 1085 1006 1031 888 937 909 1032 1006 ...
result:
ok 1000 numbers
Subtask #2:
score: 10
Accepted
Test #11:
score: 10
Accepted
time: 2434ms
memory: 28316kb
input:
50000 500000 384309433 -953786733 1 -381089810 891795502 1 -701194776 440247159 1 -403243027 539105336 1 275206790 -652250203 1 -554746251 903743804 1 -457035253 912757156 1 -342310772 -17612092 1 -440332191 682239316 1 730332275 816145283 1 -701691234 -908289789 1 -632861504 -277378843 1 -567495050...
output:
618496745 614079729 616866497 614478068 613189405 616715138 615126465 616114802 614529490 614077984 616764805 614626805 615475280 615176840 617956645 618705730 613485153 614626805 614626805 612802541 617062849 617662305 613684025 618496745 612900340 615420738 613682609 617857600 616568900 614626805 ...
result:
ok 500000 numbers
Test #12:
score: 10
Accepted
time: 2594ms
memory: 28664kb
input:
50000 500000 729905 -125985 1 926315 959640 1 123096 -91945 1 -186481 965101 1 -425756 271410 1 -158109 -800982 1 122987 441100 2 -732281 918630 1 182284 -51080 1 -380410 -929492 1 472062 848544 1 671209 376870 1 366165 -263178 1 -539467 -62456 1 942084 68081 1 384749 792849 1 -648204 -741411 2 7878...
output:
398628245 392170825 389391829 388440685 392182688 387805108 381517693 384525010 390830690 397720525 391054036 392346085 516745745 395682701 395754553 388205365 395821634 398565154 1051363802 385964164 387885617 390926962 22605145 389138933 386438306 387558676 390944065 392346085 398628245 391344637 ...
result:
ok 500000 numbers
Subtask #3:
score: 15
Accepted
Dependency #2:
100%
Accepted
Test #13:
score: 15
Accepted
time: 3739ms
memory: 39828kb
input:
50000 500000 -9418 -1818 20 7456 -4051 11 2408 1036 12 9188 -5797 26 -2810 -6058 10 -1870 -5476 15 -4838 3308 10 -7573 -547 12 -8221 -6779 58 4436 -6839 78 -5131 -5558 31 -636 7994 15 3144 8637 2 -9161 -7142 63 -5699 -3454 72 -5585 3911 7 6193 -8685 68 6768 1154 37 -5097 -5253 9 7322 6256 8 -4366 71...
output:
12323846 12427135 12344036 12062617 12466352 11630227 12036161 12050157 12062549 12419726 20506205 12059447 12027445 12313309 12216296 10607828 0 15278549 15242701 48910334 12548226 12076087 12062617 13714531 12245560 12030548 12017793 18674164 12056369 12691062 12435069 12440010 48910334 12163067 1...
result:
ok 500000 numbers
Test #14:
score: 15
Accepted
time: 3593ms
memory: 40084kb
input:
50000 500000 877025 350139 5 -143832 444608 43 455083 449721 13 21366 -923804 47 540152 789728 71 266227 355382 63 -536428 -711034 23 -998154 57875 8 -334074 740620 32 246276 374916 3 -704297 -393685 33 -614894 880828 73 117185 415990 1 -543312 215046 31 215904 -404000 30 -427829 90281 1 427722 -832...
output:
12473373 12408257 12507154 12376650 12213364 12336818 12461889 12194343 12487088 12461889 12287636 12476420 12138920 12375917 12204989 12291029 12374246 12190029 12205841 12475690 12469649 12294925 12269579 12287636 12482573 12465762 12289822 12297787 12462205 12205841 12328257 12465379 12304117 122...
result:
ok 500000 numbers
Test #15:
score: 15
Accepted
time: 2843ms
memory: 34932kb
input:
50000 500000 875409176 -146884605 3 -852555067 779442669 2 -135310615 -25991150 1 -415857031 995015289 37 -761492260 48848870 18 -207602077 -813247088 1 162687832 10213336 1 271929112 682994180 2 -76574267 131873021 1 -368335679 549046786 1 352160629 -463359855 2 782068089 825319998 3 -44672214 4112...
output:
76232923 76121667 75960552 76119621 75585987 75598132 75867079 75861652 75979823 75793380 75639606 75763031 76442133 76022093 76141936 76272184 76131346 75871360 76193620 76011967 75613338 75766062 75994345 75790820 76032783 75617428 75694697 75905128 76046280 75625683 75700183 76007971 76041513 760...
result:
ok 500000 numbers
Test #16:
score: 15
Accepted
time: 2656ms
memory: 34824kb
input:
50000 500000 -598585200 546145949 4 10693995 -846396922 14 789052862 -37923989 1 -492717756 388481199 3 -813901947 -942867382 1 -205123361 865058110 10 221165729 -989130173 7 843701647 164674253 6 -454532857 559818222 3 257996198 793738572 1 775938225 -262839196 1 834834185 -519682962 5 94950096 -12...
output:
149944516 152615583 152192654 149944516 149315628 150312655 152169394 148653173 150202721 151318447 150149019 152077654 150002507 150022335 151425709 152151682 150174510 151274436 150151257 152150221 148682034 149995028 149839542 148012905 153950049 150174510 146646463 150553151 149944516 151744655 ...
result:
ok 500000 numbers
Test #17:
score: 15
Accepted
time: 2479ms
memory: 32544kb
input:
50000 500000 378393334 246666269 3 -288429751 -689240591 1 538246474 -179149420 4 19866140 -274604312 1 319383040 694674452 2 9044676 284630066 1 -577379922 -799429128 1 753882987 742757782 1 -748336557 -508913081 1 -744458940 -766779721 1 629312624 888874873 1 345082535 -233888060 9 -198240179 6127...
output:
355919371 357027423 356882073 348068675 341563980 341711918 341993252 351216013 341820581 341247927 355801139 357012424 360549504 345514553 346612456 355801139 345629345 348188018 331432712 334365769 345187709 355645668 353004772 345187709 330517432 341711918 355838156 337808150 331333696 347288304 ...
result:
ok 500000 numbers
Test #18:
score: 15
Accepted
time: 3258ms
memory: 40388kb
input:
50000 500000 510087025 -128717769 4 701695438 891659838 17 14091267 -407206760 13 -897701961 -347902519 32 -208038559 -712604275 54 352114405 -467350403 25 665063400 239362902 78 108580609 -287322505 20 979576161 450624747 6 -351660808 883871753 30 626923938 -181807026 32 224172685 -215957127 18 -12...
output:
12457570 12211756 12089072 12451033 12298688 12439757 12320487 12457570 12457570 12317459 12215044 12190106 12226306 12213127 12302925 12067172 12241961 12233658 12442012 12162881 12239648 12467217 12244792 12194336 12312968 12304959 12388042 12468644 12457570 12287858 12241961 12473476 12223586 120...
result:
ok 500000 numbers
Subtask #4:
score: 15
Accepted
Test #19:
score: 15
Accepted
time: 2946ms
memory: 38924kb
input:
50000 500000 2598 -1000000 6 1388 -1000000 3 5492 1000000 8 -1000000 -3573 23 -1000000 -7880 15 -4285 1000000 7 1000000 5211 5 -1000000 5915 79 7147 -1000000 29 -9495 -1000000 25 9028 1000000 1 1000000 -4880 20 -8498 1000000 53 1000000 -4256 22 3107 -1000000 29 2061 -1000000 45 8876 -1000000 76 -279...
output:
12162691 12234856 12164084 12162691 12161484 12164084 12162691 12157836 12258260 12231963 12236398 12176350 12164084 12225490 12162691 12237049 12226003 12164084 12237262 12162691 12164084 12234856 12226003 12234856 12162691 12237049 48739336 12214677 12162691 12256061 12162691 12162691 12164084 122...
result:
ok 500000 numbers
Test #20:
score: 15
Accepted
time: 3270ms
memory: 38716kb
input:
50000 500000 576582 1000000 4 1000000 161459 39 739803 1000000 8 -485360 1000000 26 1000000 744458 19 -228118 1000000 64 1000000 419390 19 -1000000 569320 24 -145848 1000000 22 1000000 858215 6 477886 1000000 62 -409508 1000000 7 -372947 1000000 42 339291 1000000 20 -127924 -1000000 8 -173305 -10000...
output:
12128001 10147483 12271607 12005528 12077544 12008061 12167783 12268758 12078530 12204095 12144712 12224065 12271607 12268261 12059600 12094342 12203334 12077544 12152901 12174157 12075772 12202316 12205623 12033183 12087956 12123445 12203060 12008061 12269532 12271607 12161125 12042827 12206274 120...
result:
ok 500000 numbers
Test #21:
score: 15
Accepted
time: 2652ms
memory: 33656kb
input:
50000 500000 126515 1000000 19 236387 -1000000 1 -1000000 148245 1 -565426 1000000 3 710526 -1000000 2 -1000000 -646115 13 -572407 1000000 30 1000000 133953 3 388708 -1000000 6 -1000000 -179731 2 149471 -1000000 1 -1000000 -326143 1 606328 -1000000 1 -1000000 302009 2 1000000 335549 1 -707858 100000...
output:
155342703 74345734 73024939 61763727 75852234 73026551 72683378 74373429 74957848 75154387 75517146 74188795 73013333 75442641 75888697 74373429 74188795 73219096 74350501 74188795 72761100 74266082 75529720 74200930 74353768 74194749 74156803 74202990 73013333 73082645 72776608 74375640 75304832 74...
result:
ok 500000 numbers
Test #22:
score: 15
Accepted
time: 2508ms
memory: 33120kb
input:
50000 500000 -1000000 385771 5 1000000 176561 1 -692051 1000000 3 515107 -1000000 1 731253 -1000000 1 1000000 729714 3 -799067 -1000000 3 -1000000 114094 2 291915 -1000000 5 827002 1000000 1 -1000000 57799 2 1000000 -60543 1 -1000000 -855569 3 -439007 1000000 26 -1000000 301693 11 -972189 1000000 3 ...
output:
147448504 144790197 148620892 150950131 149817983 148226985 150132615 147630517 144729753 149206551 149774272 151232237 144737201 148263444 147772235 146233220 151262581 149232259 149774143 148422230 149279553 148339714 151285621 146234259 147901505 149971237 148291338 147408606 146234259 150691646 ...
result:
ok 500000 numbers
Test #23:
score: 15
Accepted
time: 2339ms
memory: 32264kb
input:
50000 500000 1000000 890913 1 638628 -1000000 1 687613 -1000000 2 -1000000 895922 2 -1000000 -279395 2 1000000 -658612 5 -1000000 28121 1 900969 -1000000 1 628213 -1000000 1 -1000000 695171 1 -94068 -1000000 1 -807382 -1000000 1 969781 -1000000 1 -1000000 136913 1 -199349 -1000000 1 224379 1000000 1...
output:
345507542 345465896 343480287 344079714 343480287 342939383 343301341 385454227 344959364 295826451 346533348 343480287 344193667 345699221 343480287 342750287 344015267 344959364 343725445 342866160 263869621 344193667 344200661 343087537 344180503 342784119 205686034 0 346323976 344959364 34471673...
result:
ok 500000 numbers
Test #24:
score: 15
Accepted
time: 3084ms
memory: 33216kb
input:
50000 500000 183079 1000000 13 -75365 -1000000 60 -574128 -1000000 22 -1000000 182234 72 -508401 1000000 51 1000000 393662 34 -641022 -1000000 28 -1000000 396945 4 210789 1000000 3 -975146 1000000 55 1000000 368734 10 -466467 1000000 42 -567699 -1000000 18 -1000000 -172812 33 1000000 526746 17 10000...
output:
11525523 12324957 12174748 12113017 12154047 12075315 12265839 11918589 12271963 12268993 90255 12399500 12398632 12269140 12241815 12433143 11939365 12229072 11985924 12269601 11984358 16880277 12113017 12443624 12394845 11985924 12398632 12357940 11952828 12320399 1893151 12267128 12398211 1212672...
result:
ok 500000 numbers
Subtask #5:
score: 15
Accepted
Test #25:
score: 15
Accepted
time: 3726ms
memory: 40332kb
input:
50000 500000 407 -5105 53 6211 98 81 7444 6196 1 -4294 -9353 26 4316 -3143 1 7144 2361 17 6364 -2245 14 -8684 -6564 3 6269 -687 2 -3139 5693 12 -9991 6547 20 2179 2178 47 -6588 7830 21 -6216 -200 3 9207 8834 24 9388 -5953 31 7752 4125 39 7875 -5517 22 -4701 2244 12 8088 3158 4 -4446 3467 1 -1002 154...
output:
10325005 11474809 0 0 11518032 0 0 49015742 49015742 49015742 0 11392831 0 49015742 0 13876057 0 13339251 10553686 49015742 49015742 49015742 14634637 0 0 49015742 49015742 0 11099497 49015742 11282162 0 0 49015742 0 49015742 0 49015742 49015742 49015742 0 49015742 13190125 13266876 0 0 10953869 116...
result:
ok 500000 numbers
Test #26:
score: 15
Accepted
time: 4098ms
memory: 38884kb
input:
50000 500000 -798827 -248238 55 -202385 195966 51 -935972 695372 12 -207494 597523 36 828639 839545 1 604085 -878258 28 854907 987889 33 -488652 555674 10 -308758 201373 2 786438 -72867 11 -533482 -614535 58 -853349 714523 60 729730 441018 27 193712 759574 30 -439466 -262414 1 -995124 383459 76 5638...
output:
12116545 1627120 12028488 8327000 11890527 12038075 12100532 30829152 23884384 48253618 0 0 48253618 12079058 4707441 34295749 1085217 12123770 48253618 20695368 11904819 3608287 12253559 0 12074236 12265677 12236373 48253618 12250929 0 11885547 11885547 7336386 12109428 48253618 0 0 36922388 511026...
result:
ok 500000 numbers
Test #27:
score: 15
Accepted
time: 3215ms
memory: 35072kb
input:
50000 500000 916228474 736861331 8 41223569 567024226 2 33633521 -640602439 11 43060388 157896754 9 522582493 -456464181 2 184581697 729182371 8 -915463955 774500464 2 595541741 4861507 3 375567184 -686285601 3 -59758078 -72014188 11 -535452680 -972290610 4 -425062848 998970443 3 776900364 383068694...
output:
73688076 34624304 35713642 74151261 74568055 73687317 80280672 73694989 74197031 74197031 190116467 73477393 74568055 23847839 86652478 126942497 108464771 74197031 125422244 56618750 74568055 73657436 9934358 85804146 74568055 221183265 178732347 73330257 73172655 74197031 73622903 74619669 7449609...
result:
ok 500000 numbers
Test #28:
score: 15
Accepted
time: 3107ms
memory: 33924kb
input:
50000 500000 -218467527 996547968 2 667898126 353067063 1 -703792310 -88011029 3 796101380 -150592337 1 233483304 202627437 1 227009907 -277641383 1 398753734 123601516 1 -932943038 -991506612 1 -586877275 884068330 1 -14924328 992992981 15 -558045242 470672933 7 -305045173 -532112183 7 183202586 80...
output:
34171044 145124721 133863158 322891322 149231859 144059207 201503200 147989909 145302374 145382184 145302231 144074835 144074694 186273717 391942339 147909184 145382184 147909184 45485862 30564622 147909184 13602211 29269333 136955300 161713859 145417496 411765627 144050978 147901245 147744158 30332...
result:
ok 500000 numbers
Test #29:
score: 15
Accepted
time: 3027ms
memory: 33944kb
input:
50000 500000 -209258179 -13673102 2 -536850965 -914833237 1 -859835086 -387099479 7 650316207 -949976551 2 490090099 432733293 1 295590818 336348152 1 -924146823 -481896977 1 -688990212 -402275949 1 905552333 225834084 1 100755207 -115968339 5 409919132 761133402 1 -486717813 -425455505 1 -448210451...
output:
342217921 351225756 335443425 351262509 109504291 342519167 344283077 344283077 335848738 803468818 538859665 335443425 344283077 344548834 351534475 335399668 765872733 216202376 344283077 335363755 351409541 51890336 201074052 335443425 351534475 335363755 351452899 124534601 342217921 351828683 3...
result:
ok 500000 numbers
Test #30:
score: 15
Accepted
time: 3651ms
memory: 39284kb
input:
50000 500000 -683034611 -711257501 27 60004722 -761142590 25 661166166 -468685357 7 849005124 -979617930 65 -844130034 690778896 26 420045533 -127259351 21 770352203 284425974 4 767529443 -311119877 25 -773073204 -708678356 61 -616770488 -127741421 27 -439194801 -804840917 7 -102517861 -591985498 15...
output:
5176455 36752777 12349440 9037077 11988285 12249163 12230497 6719556 12344687 12249163 11988285 12055113 31826512 12074401 15191922 32592923 12074401 12358058 10249606 12249163 11988285 12009512 12074401 12067085 11988285 12074401 12345034 12349440 12074401 11998182 12074401 23409470 1079840 2820121...
result:
ok 500000 numbers
Subtask #6:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #31:
score: 10
Accepted
time: 1015ms
memory: 25220kb
input:
20000 200000 6638 9179 76 -6000 442 3 3879 -6574 7 8687 4572 8 3147 5179 38 253 -9723 3 -7740 -1232 4 -3694 -5085 2 404 8299 31 -7760 -1678 9 -1545 2578 10 -1619 -3470 60 8213 5421 30 3532 -3882 33 -7243 -4051 16 8061 7004 47 -1210 -2676 7 466 1969 20 4548 1421 34 -7818 -6690 5 -4934 -9618 1 -2580 -...
output:
1758698 7647866 0 7647866 7647866 7647866 7647866 0 1635548 0 0 1653656 1748652 7647866 0 0 0 1818126 0 1670265 7647866 7647866 7647866 117560 7647866 2211850 7647866 1706734 7647866 3819707 0 7647866 7647866 0 0 2005011 0 2081748 0 0 0 7647866 7647866 0 7647866 0 7647866 0 7647866 7647866 1853071 0...
result:
ok 200000 numbers
Test #32:
score: 10
Accepted
time: 1089ms
memory: 25272kb
input:
20000 200000 78296 871705 2 -321786 -223939 55 206321 13301 5 936459 953224 2 786679 -207659 4 -344982 138785 7 -679393 625365 23 471779 -234292 4 309023 387746 40 552469 -85365 47 -249315 -212920 17 760830 -73928 6 372279 -74882 67 250928 40245 2 113230 893088 24 825605 -900412 16 -97442 20555 38 4...
output:
0 1977860 4936377 7696888 1954788 5786368 215261 1526406 0 1960128 0 1872175 7696888 0 3348197 1900942 457581 135358 0 178251 1957422 190903 0 7696888 1899809 0 1877839 1956585 831741 1980824 7696888 1877230 1983876 1983161 7696888 1894267 1877839 1901712 0 0 7696888 1313985 125818 0 526858 1962369 ...
result:
ok 200000 numbers
Test #33:
score: 10
Accepted
time: 791ms
memory: 26928kb
input:
20000 200000 652486619 -31021686 3 674095691 464638171 4 15422233 759985277 3 562107322 412005266 1 139860761 796741739 8 698712467 -590901499 1 522238215 626704636 1 201348077 -408723082 1 39872091 715972308 1 796098329 -286661044 2 919206004 -469492740 1 -383301172 -29536420 3 53882519 861839374 2...
output:
11771013 31274335 11879033 35912140 11726284 4205341 11733792 11717495 12782396 11771013 11771013 10070328 11869954 23720452 11771013 11879033 22429986 11922585 11722958 11879033 31338181 20862487 11879033 9810882 11879033 11726284 11892271 23710360 11278574 11929578 11771013 11712074 11879033 52664...
result:
ok 200000 numbers
Test #34:
score: 10
Accepted
time: 756ms
memory: 24280kb
input:
20000 200000 -795353471 115084011 13 -563296752 -456325938 1 -674289346 95689857 1 -92044055 754798599 9 -675839663 21811860 1 506687221 -419286981 2 -884311516 -454927818 2 -755930287 188852928 1 -581091496 -419381474 3 -728317641 229096947 1 338056790 -39273736 19 -210691940 -469787431 1 -38255758...
output:
1912895 23547122 23547122 23844021 24004015 18462397 62340461 24036205 5430123 24004015 23567973 23825729 9884613 23844021 66985157 23466766 21626963 23400133 69769389 23864900 24023548 2171328 23469795 2845135 23400133 23864900 16852015 23844021 67005381 23795237 23616691 9291007 23586309 23937167 ...
result:
ok 200000 numbers
Test #35:
score: 10
Accepted
time: 691ms
memory: 24444kb
input:
20000 200000 597487142 -264327080 1 363097870 -93832409 2 -133170749 -255087340 1 -93165077 880837061 2 -776244068 -942115532 1 -66302342 914936080 1 -543471400 321627441 1 -763297145 903202513 1 964264167 997147840 1 404083309 -28792558 1 7173459 -840908932 1 -133986760 895564657 1 913858985 -98644...
output:
32223218 53872063 55494198 144056178 140092438 32866170 23323015 54143424 53961016 54056940 53872063 22182709 53797992 97450256 55523430 54071349 53872063 88284830 93898674 154834759 4565025 53872063 55215190 82673062 55584499 54071349 53872063 54143424 55494198 124251547 55310638 55584499 10314775 ...
result:
ok 200000 numbers
Test #36:
score: 10
Accepted
time: 966ms
memory: 28340kb
input:
20000 200000 -941638561 360399266 28 933472562 827467156 29 142596199 -312313142 19 -701859452 784478711 53 -167771199 -602390645 67 -232270233 571628419 12 252628776 98913281 37 239060250 520487898 35 80892487 -258989235 28 44250745 868627770 45 132973358 -275683185 14 884510982 108814973 66 903390...
output:
1968291 1970567 1934739 1936879 1968291 1936879 1963847 1956137 3933707 1494847 1936879 945467 5455966 430262 1936879 1963847 1950287 3124096 1954982 642280 1953891 363771 1954805 1958139 1956137 1956000 4377693 1932276 1936879 1968291 1934739 4995468 1952387 1936879 1936879 1952387 1288909 5187460 ...
result:
ok 200000 numbers
Subtask #7:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #37:
score: 30
Accepted
time: 3714ms
memory: 40216kb
input:
50000 500000 1589 8463 1 1266 2707 26 -3781 -4886 1 -5197 -3351 26 -9404 -8495 69 -5626 -5650 6 -6406 3862 6 -9554 333 63 9345 6143 4 9999 -5422 6 -1057 3347 4 -1875 4755 49 9262 7572 9 -7656 -2969 30 -1409 58 2 4007 -5531 18 9075 -7976 2 -3351 -6235 8 -8015 -4979 16 -3007 6154 38 384 1157 98 229 -7...
output:
0 48745672 48745672 48745672 48745672 43631262 9977015 48745672 48745672 0 0 48745672 0 13398339 13064635 48745672 0 0 0 0 48745672 10666623 48745672 48745672 10237863 11852573 48745672 48745672 0 0 48745672 14122702 0 0 0 10019374 14313714 48745672 0 0 11387675 48745672 48745672 0 48745672 48745672...
result:
ok 500000 numbers
Test #38:
score: 30
Accepted
time: 4091ms
memory: 39028kb
input:
50000 500000 -739737 366035 51 -442016 307988 2 -2281 -540794 6 -206781 253599 50 809677 -492852 25 -591794 -10928 39 775405 -389436 14 -753300 475635 35 -37220 -344043 40 645046 377835 69 -550065 -460884 75 -831546 -627707 81 826454 152706 37 -900347 -411552 38 876842 -22856 6 -834316 481330 28 -30...
output:
49035156 12205267 0 12313280 3341704 21634378 12215150 0 0 31495590 12207787 16893932 12328959 2929505 12335605 12215662 0 0 12232081 1735474 12335605 49035156 3309472 2886993 0 23333460 49035156 26728284 5423041 0 49035156 24494620 16709465 13569983 12242793 20966588 0 12242793 49035156 12309395 34...
result:
ok 500000 numbers
Test #39:
score: 30
Accepted
time: 3175ms
memory: 33960kb
input:
50000 500000 -18414141 -335014110 3 730714967 -362617039 19 -379375488 965434127 1 -371694886 222500187 6 501205050 -189468127 1 811398401 -124713275 2 318073388 835845779 5 -431968481 637329234 2 34202047 -932137882 1 -389625683 307774657 14 -702154554 -301179013 18 378551891 -493417029 18 -7646025...
output:
74419796 74825637 74333767 75077882 74333767 7379556 74950526 74951811 75077882 74503425 74482204 74480695 74333767 74333767 9063616 74480695 11541068 74951811 163409491 74480695 74480695 74975228 74468768 74905305 74858851 76091502 75027534 186517607 74506956 74977047 22096350 74813127 13467078 148...
result:
ok 500000 numbers
Test #40:
score: 30
Accepted
time: 3068ms
memory: 33568kb
input:
50000 500000 -898974254 -272015859 2 524643792 -677351300 1 -346347507 -663490567 1 -987821904 3326366 1 275583702 -484911625 1 621328805 -236251887 1 723918831 -145063306 1 -474909259 481664284 1 -447389176 507119972 5 -65897181 -663619497 5 -183566661 479573094 2 -620440731 515322609 16 -190635115...
output:
143717486 293122492 147850604 10258568 144005056 148016056 147850604 391519154 212453146 144622282 144253110 147327277 146980937 147850604 185164271 144299465 147283545 147283545 144391737 147283545 212991346 147283545 125855038 148016056 127149890 147944768 144274757 143717486 21641894 19734726 143...
result:
ok 500000 numbers
Test #41:
score: 30
Accepted
time: 2953ms
memory: 32880kb
input:
50000 500000 297150884 -678281836 1 -235259590 583759680 2 -345824587 239257713 2 640549106 305743977 1 -224115664 -211437114 1 -213899271 -343874529 1 -429661975 -493173481 5 -298410417 133979858 7 -720939592 841106465 1 -370668382 -352857711 1 831175296 657730068 1 -787526773 -983123445 1 17226381...
output:
339470171 346791250 346791250 343418023 336139128 339470171 336139128 339470171 417641276 342374713 343418023 1025531031 336139128 336217785 339470171 346791250 346791250 346900831 343075283 335730219 336139128 343806081 117750576 343229827 343454358 339657267 346625567 339470171 339470171 516970422...
result:
ok 500000 numbers
Test #42:
score: 30
Accepted
time: 3589ms
memory: 38096kb
input:
50000 500000 507692522 -356531616 17 -499049437 -828620276 41 -461066400 -120051101 51 -955895608 269917649 24 168567044 -419298606 4 830731508 949329320 51 -77162086 -46979408 50 230437298 132203808 22 -905004502 268234642 13 202971180 -724817526 20 -295919146 520614939 60 -996188279 462572105 32 -...
output:
31139693 30148805 12201551 12038470 12245300 12247207 12249744 12038470 13489546 37147051 12220688 12024691 12024691 12230005 12230005 1841710 11933752 32643539 3892462 5240375 12024691 12007541 12014222 18130359 12249209 12220688 2987977 12017434 29008887 12038470 13362112 12018893 12220688 1202469...
result:
ok 500000 numbers