QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93979 | #4409. 袜子 | chenshi | 25 | 10189ms | 65756kb | C++ | 3.2kb | 2023-04-04 12:58:02 | 2023-04-04 12:58:07 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int o=5e5+10,B=800;
int n,m,X[o],Y[o],col[o],a[o],b[o],c[o],p[o],idinv[o],cnt[o],tot[o],e[o];long long d[o],ans[o];vector<int> vec[o];
struct Query{int a,b,c;};
struct Slope{
int x,y;
Slope(int x_,int y_):x(x_),y(y_){}
inline int Quadrant()const{
if((x==0&&y<0)||(x>0&&y<0)) return 0;
if((x>0&&y==0)||(x>0&&y>0)) return 1;
if((x==0&&y>0)||(x<0&&y>0)) return 2;
return 3;
}
inline bool operator<(const Slope&b)const{
if(Quadrant()^b.Quadrant()) return Quadrant()<b.Quadrant();
return x*1ll*b.y-y*1ll*b.x>0;
}
};
namespace foobar{
int n,A,B;bool typ;vector<int> id;vector<pair<Slope,pair<int,int> > > s;
inline int lowbit(int x){return x&-x;}
inline void modify(int pos,int val){for(++pos;pos<=n;pos+=lowbit(pos)) d[pos]+=val;}
inline long long query(int pos){long long res=0;for(++pos;pos;pos-=lowbit(pos)) res+=d[pos];return res;}
inline bool Cmp(int i,int j){return A*1ll*X[i]+B*1ll*Y[i]<A*1ll*X[j]+B*1ll*Y[j];}
inline void slv(){
if(id.empty()) return;
n=id.size();vector<pair<Slope,pair<int,int> > >().swap(s);
A=0;B=-1;sort(id.begin(),id.end(),Cmp);
for(int i=0;i<n;++i) for(int j=i+1,x,y;j<n;++j){
x=X[id[j]]-X[id[i]],y=Y[id[j]]-Y[id[i]];
Slope t1(y,-x),t2(-y,x);
if(t2<t1) swap(t1,t2);
s.push_back(make_pair(t1,make_pair(id[i],id[j])));s.push_back(make_pair(t2,make_pair(id[j],id[i])));
}
sort(s.begin(),s.end());
for(int i=0;i<n;++i) idinv[id[i]]=i,d[i+1]=0;
if(!typ) for(int i=0;i<n;++i) e[i]=tot[col[id[i]]]++,modify(i,e[i]);
for(int i=1,j=0,sz=s.size(),l,r,md;i<=m;++i){
for(int x,y;j<sz&&s[j].first<Slope(a[p[i]],b[p[i]]);++j){
x=idinv[s[j].second.first];y=idinv[s[j].second.second];
if(x>y) continue;
if(!typ){
modify(x,-e[x]);modify(y,-e[y]);
for(int k=x+1;k<y;++k){
if(col[id[x]]==col[id[k]]) --e[k],modify(k,-1),++e[x];
if(col[id[y]]==col[id[k]]) ++e[k],modify(k,1),--e[y];
}
if(col[id[x]]==col[id[y]]) ++e[x],--e[y];
swap(e[x],e[y]);
modify(x,e[x]);modify(y,e[y]);
}
swap(id[x],id[y]);swap(idinv[id[x]],idinv[id[y]]);
}
for(l=-1,r=n-1;l<r;){
md=(l+r+1)/2;
if(a[p[i]]*1ll*X[id[md]]+b[p[i]]*1ll*Y[id[md]]+c[p[i]]<0) l=md;
else r=md-1;
}
if(typ) cnt[p[i]]+=l+1;
else ans[p[i]]+=query(l)*2+l+1;
}
vector<int>().swap(id);typ=0;
}
}
inline bool cmp(int A,int B){return Slope(a[A],b[A])<Slope(a[B],b[B]);}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d%d%d",&X[i],&Y[i],&col[i]),vec[col[i]].push_back(i);
for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i],&b[i],&c[i]),p[i]=i;
sort(p+1,p+m+1,cmp);
for(int i=1;i<=n;++i) if((int)vec[i].size()>=B){
for(int j=1;j<=m;++j) cnt[j]=0;
for(int j=0,sz=vec[i].size();j<sz;++j){
if(j%B==0) foobar::slv(),foobar::typ=1;
foobar::id.push_back(vec[i][j]);
}
foobar::slv();
for(int j=1;j<=m;++j) ans[j]+=cnt[j]*1ll*cnt[j];
}
for(int i=1;i<=n;++i) if(!vec[i].empty()&&(int)vec[i].size()<B){
if((foobar::id.size()+vec[i].size())>B) foobar::slv();
for(int j=0,sz=vec[i].size();j<sz;++j) foobar::id.push_back(vec[i][j]);
}
foobar::slv();
for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 147ms
memory: 45684kb
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: 0
Accepted
time: 141ms
memory: 46784kb
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: 0
Accepted
time: 133ms
memory: 45432kb
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: 0
Accepted
time: 167ms
memory: 44768kb
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: 0
Accepted
time: 145ms
memory: 45472kb
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: 0
Accepted
time: 138ms
memory: 44656kb
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: 0
Accepted
time: 138ms
memory: 44572kb
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: 0
Accepted
time: 132ms
memory: 48600kb
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: 0
Accepted
time: 142ms
memory: 46448kb
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: 0
Accepted
time: 149ms
memory: 48140kb
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: 9268ms
memory: 64420kb
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: 0
Accepted
time: 9375ms
memory: 64696kb
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: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #13:
score: 0
Wrong Answer
time: 10189ms
memory: 65160kb
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:
wrong answer 591st numbers differ - expected: '14118464', found: '14116539'
Subtask #4:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 9695ms
memory: 65252kb
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:
wrong answer 348th numbers differ - expected: '12173369', found: '12171486'
Subtask #5:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 8899ms
memory: 64768kb
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:
wrong answer 78045th numbers differ - expected: '36210682', found: '36211053'
Subtask #6:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #31:
score: 10
Accepted
time: 3019ms
memory: 64336kb
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: 0
Accepted
time: 3060ms
memory: 64224kb
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: 0
Accepted
time: 2953ms
memory: 65756kb
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: 0
Accepted
time: 3093ms
memory: 62088kb
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: 0
Accepted
time: 2989ms
memory: 62340kb
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: 0
Accepted
time: 3000ms
memory: 65172kb
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: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%