QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526650#4409. 袜子Displace_100 ✓4098ms40388kbC++147.3kb2024-08-21 19:08:142024-08-21 19:08:14

Judging History

你现在查看的是最新测评结果

  • [2024-08-21 19:08:14]
  • 评测
  • 测评结果:100
  • 用时:4098ms
  • 内存:40388kb
  • [2024-08-21 19:08:14]
  • 提交

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