QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354217#8286. Stacksucup-team134#AC ✓705ms934844kbC++174.4kb2024-03-14 23:44:362024-03-14 23:44:37

Judging History

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

  • [2024-03-14 23:44:37]
  • 评测
  • 测评结果:AC
  • 用时:705ms
  • 内存:934844kb
  • [2024-03-14 23:44:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=100050;

namespace MergeST {
	const int M=40000000;
	int ls[M],rs[M],tsz;
	ll sum[M],cnt[M];
	ll val[N];

	int cpy(int c){
		++tsz;
		sum[tsz]=sum[c];
		cnt[tsz]=cnt[c];
		ls[tsz]=ls[c];
		rs[tsz]=rs[c];
		return tsz;
	}
	void Add(int&c,int ss,int se,int qi,ll x,ll y){
		c=cpy(c);
		sum[c]+=x*y;
		cnt[c]+=x;
		if(ss==se)return;
		int mid=ss+se>>1;
		if(qi<=mid)Add(ls[c],ss,mid,qi,x,y);
		else Add(rs[c],mid+1,se,qi,x,y);
	}
	void Merge(int&c,int l,int r,int ss,int se){
		if(!l||!r)c=l^r;
		else{
			c=++tsz;
			sum[c]=sum[l]+sum[r];
			cnt[c]=cnt[l]+cnt[r];
			int mid=ss+se>>1;
			Merge(ls[c],ls[l],ls[r],ss,mid);
			Merge(rs[c],rs[l],rs[r],mid+1,se);
		}
	}
	void pull(int c){
		sum[c]=sum[ls[c]]+sum[rs[c]];
		cnt[c]=cnt[ls[c]]+cnt[rs[c]];
	}
	void Cut(int&c,int ss,int se,ll k){
		if(cnt[c]<=k)return;
		c=cpy(c);
		if(ss==se){
			if(cnt[c]>k){
				sum[c]-=val[ss]*(cnt[c]-k);
				cnt[c]=k;
			}
			return;
		}
		int mid=ss+se>>1;
		if(cnt[ls[c]]>=k){
			rs[c]=0;
			Cut(ls[c],ss,mid,k);
			pull(c);
		}else{
			Cut(rs[c],mid+1,se,k-cnt[ls[c]]);
			pull(c);
		}
	}
	ll Get(int c,int ss,int se,ll k){
		if(ss==se){
			return val[ss]*min(k,cnt[c]);
		}
		int mid=ss+se>>1;
		if(cnt[ls[c]]<=k){
			return Get(rs[c],mid+1,se,k-cnt[ls[c]])+sum[ls[c]];
		}
		return Get(ls[c],ss,mid,k);
	}
}


int t[N];
ll l[N],r[N],x[N],y[N];
int when[N],tid,n,m;

namespace ST{
	const int M=2*N;
	int ls[M],rs[M],tsz,root;
	int rt[M],sub[M];

	void Build(int &c,int ss,int se){
		c=++tsz;
		if(ss==se)return;
		int mid=ss+se>>1;
		Build(ls[c],ss,mid);
		Build(rs[c],mid+1,se);
	}

	void cut(int c,ll k){
		if(MergeST::cnt[rt[c]]>k){
			MergeST::Cut(rt[c],1,tid,MergeST::cnt[rt[c]]-k);
		}else{
			sub[c]+=k-MergeST::cnt[rt[c]];
			rt[c]=0;
		}
	}

	void push(int c){
		if(sub[c]>0){
			cut(ls[c],sub[c]);
			cut(rs[c],sub[c]);
			sub[c]=0;
		}
		if(MergeST::cnt[rt[c]]>0){
			MergeST::Merge(rt[ls[c]],rt[ls[c]],rt[c],1,tid);
			MergeST::Merge(rt[rs[c]],rt[rs[c]],rt[c],1,tid);
			rt[c]=0;
		}
	}

	void Add(int c,int ss,int se,int qs,int qe,int idx,ll x,ll y){
		if(qs>qe||qs>se||ss>qe)return;
		if(qs<=ss&&qe>=se){
			MergeST::Add(rt[c],1,tid,idx,x,y);
			return;
		}
		int mid=ss+se>>1;
		push(c);
		Add(ls[c],ss,mid,qs,qe,idx,x,y);
		Add(rs[c],mid+1,se,qs,qe,idx,x,y);
	}

	void Del(int c,int ss,int se,int qs,int qe,ll k){
		if(qs>qe||qs>se||ss>qe)return;
		if(qs<=ss&&qe>=se){
			cut(c,k);
			return;
		}
		int mid=ss+se>>1;
		push(c);
		Del(ls[c],ss,mid,qs,qe,k);
		Del(rs[c],mid+1,se,qs,qe,k);
	}

	int GetTree(int c,int ss,int se,int qi){
		if(ss==se)return rt[c];
		int mid=ss+se>>1;
		push(c);
		if(qi<=mid)return GetTree(ls[c],ss,mid,qi);
		return GetTree(rs[c],mid+1,se,qi);
	}
}


int main(){
	scanf("%i %i",&n,&m);
	vector<int> ids;
	for(int i=1;i<=m;i++){
		scanf("%i",&t[i]);
		if(t[i]==1){
			scanf("%lld %lld %lld %lld",&l[i],&r[i],&x[i],&y[i]);
		}else if(t[i]==2){
			scanf("%lld %lld %lld",&l[i],&r[i],&x[i]);
		}else{
			scanf("%lld %lld %lld",&x[i],&l[i],&r[i]);
			ids.pb(x[i]);
		}
	}
	sort(ids.begin(),ids.end());
	ids.erase(unique(ids.begin(),ids.end()),ids.end());
	for(int i=1;i<=m;i++){
		if(t[i]<=2){
			l[i]=lower_bound(ids.begin(),ids.end(),l[i])-ids.begin()+1;
			r[i]=upper_bound(ids.begin(),ids.end(),r[i])-ids.begin();
			if(l[i]<=r[i]){
				if(t[i]==1){
					when[i]=++tid;
					MergeST::val[tid]=y[i];
				}
			}
		}else{
			x[i]=lower_bound(ids.begin(),ids.end(),x[i])-ids.begin()+1;
		}
	}
	n=ids.size();

	ST::Build(ST::root,1,n);

	for(int i=1;i<=m;i++){
		if(t[i]==1){
			if(l[i]<=r[i]){
				ST::Add(ST::root,1,n,l[i],r[i],when[i],x[i],y[i]);
			}
		}else if(t[i]==2){
			if(l[i]<=r[i]){
				ST::Del(ST::root,1,n,l[i],r[i],x[i]);
			}
		}else{
			int rt=ST::GetTree(ST::root,1,n,x[i]);
			ll ans=MergeST::Get(rt,1,tid,r[i])-MergeST::Get(rt,1,tid,l[i]-1);
			//for(int i=1;i<=MergeST::cnt[rt];i++)printf("%lld ",MergeST::Get(rt,1,tid,i)-MergeST::Get(rt,1,tid,i-1));
			printf("%lld\n",ans);
		}

		/*printf("After query [%i]\n",i);
		for(int j=1;j<=n;j++){
			printf("---Stack %i---\n",ids[j-1]);
			int rt=ST::GetTree(ST::root,1,n,j);
			for(int i=1;i<=MergeST::cnt[rt];i++)printf("%lld ",MergeST::Get(rt,1,tid,i)-MergeST::Get(rt,1,tid,i-1));
			printf("\n");
		}
		printf("\n");*/
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 15928kb

input:

4907 4910
2 763 3330 1
3 307 1 1
1 2262 3430 22699 89397
1 1915 4000 51541 67587
2 212 2990 9763
2 1086 2162 1
2 1813 4496 16760
1 51 2796 68005 99390
1 1267 1519 74236 66178
3 1768 23808 54314
2 900 4122 27758
3 3287 17350 28989
2 3277 4024 3633
2 444 4866 1
2 353 4219 1061
1 987 3141 99906 17320
2...

output:

0
3032090730
903396180
471569175
200648623
98486697
647114751
123945
50793012
61782451
0
0
0
762429740
321140700
871619914
536311874
5361094892
0
1792521566
6640518748
2415375780
249435711
225987900
5250788038
1145132507
140071334
0
118545795
3086405469
5646099271
84280112
1232466642
4992966775
7968...

result:

ok 1622 numbers

Test #2:

score: 0
Accepted
time: 11ms
memory: 16152kb

input:

4992 4958
2 2965 3892 1
3 2141 1 1
3 4963 1 1
3 2298 1 1
3 2236 1 1
1 3393 4668 65533 8224
1 884 2343 86158 41289
3 4617 12174 63763
2 898 4236 44143
2 2860 4246 1
2 2696 3014 1
2 496 1635 15779
3 2230 8262 39805
2 3287 3627 5350
2 3443 4900 19874
1 535 1622 26926 88406
1 3272 3747 94290 19081
2 812...

output:

0
0
0
0
424276160
1302420216
0
393525459
0
188112684
0
38587680
696225296
717180100
2193537294
297696966
0
0
0
124461621
26876032
1609925499
0
3681040200
51602516
1502016
0
8636592
1138256753
196684293
0
16126264
959145423
58640451
1945754097
2949696960
0
3577791360
2029416288
2361290004
5882833609
...

result:

ok 1597 numbers

Test #3:

score: 0
Accepted
time: 11ms
memory: 21652kb

input:

4980 4984
1 183 4891 75896 45281
2 767 3528 1367
3 2313 45535 49112
2 529 4006 1568
2 2114 2971 3819
3 3237 30655 31381
1 2074 2176 51631 35339
3 1602 95 16082
2 1340 3727 9249
2 105 1907 11928
3 2461 15189 33999
2 1450 1956 4721
1 700 4760 3043 92859
2 329 2992 6515
3 1295 10832 40486
2 3477 4447 8...

output:

162015418
32919287
723952628
851780891
1342808055
38307726
4701651115
903944603
240532672
652952020
1168430924
2253203546
3542990917
5872603595
305017015
657095398
25321688
1834305604
0
256832266
2732654054
1757936801
1158797383
656866283
3470700279
694675745
1042863834
76284096
6705704850
475899629...

result:

ok 1645 numbers

Test #4:

score: 0
Accepted
time: 10ms
memory: 20980kb

input:

4976 4948
2 858 1218 1
1 780 1528 70910 12344
1 681 4398 25997 59182
1 4564 4692 72420 96925
1 1124 2604 98159 98651
3 4734 1 1
2 1921 3430 3373
1 3805 3909 56118 23383
2 1471 2065 23679
2 1052 1154 30740
1 1098 2180 13716 29728
1 1094 3585 2073 93894
1 2024 4201 39023 1713
3 1571 21453 96893
3 1297...

output:

0
7262943486
185110624
53327400
957813600
383014415
1539405803
896522316
1454164560
7158196459
479198625
1943839360
1189657450
23355822139
2684778350
183742084
6400082784
2310401225
2082631008
5644811789
1875949890
3185562597
7185156304
3147144197
1588457333
676240200
1122598010
8758314557
100699296...

result:

ok 1663 numbers

Test #5:

score: 0
Accepted
time: 11ms
memory: 24396kb

input:

4944 4934
1 468 4845 87517 63656
3 4756 22899 79177
1 761 1054 45331 86403
1 24 2806 46189 11490
1 2602 4446 12528 14317
3 2601 51537 65051
1 1502 3573 79699 84830
3 1998 35405 151264
1 2400 4041 95071 83748
1 2050 3772 23643 53614
3 2261 51072 236192
2 1317 1908 6197
2 949 2543 30190
1 1457 4573 33...

output:

3582496024
860310840
5337461878
10833286574
1397502876
3735482073
4207877274
17671620
10854427218
1484917319
5462491276
1497165465
1453546510
1672688712
1158344316
1014734250
3797802047
15668090927
14634073116
32337553147
2159971110
12088416736
90924880
1410366456
13829776128
12126485158
18393654569...

result:

ok 829 numbers

Test #6:

score: 0
Accepted
time: 695ms
memory: 724252kb

input:

99999 99998
1 5026 18575 27178 90423
3 30623 1 1
3 76936 1 1
1 77021 95683 84664 24734
1 46085 74886 40512 11266
3 5048 8594 22468
1 53318 77721 97151 70784
1 70645 91192 37556 13013
1 56752 56940 91812 62887
1 7928 34576 87339 69404
3 74875 32807 100970
3 22338 17221 25771
3 21421 20602 57957
3 717...

output:

0
0
1254619125
4366274868
593473604
2592655824
3657975552
5652513833
110091352
1226646296
1989326852
763582808
8205318671
1659086055
3012598941
20085582585
3242801176
17381308704
24555397019
4722824224
20308857160
899316516
38935050954
988382364
13341823621
11397759491
2449683584
5875277101
80572355...

result:

ok 49797 numbers

Test #7:

score: 0
Accepted
time: 705ms
memory: 721592kb

input:

100000 99994
3 92225 1 1
3 10037 1 1
3 74283 1 1
3 2266 1 1
3 50962 1 1
3 81075 1 1
1 503 97219 60712 28632
1 20530 96581 71439 60132
3 41317 2559 104920
1 38204 95641 16185 4127
1 81150 90487 12130 78009
3 26946 49794 94793
3 30822 94956 120229
3 3139 25745 34556
1 31304 71829 59249 1581
1 34152 81...

output:

0
0
0
0
0
0
4323380784
2361991500
1519776168
252305184
5480718598
475075230
355440252
50964960
470925609
563617236
5250822628
167047570
5642890643
263790112
16650744580
9469618067
1523342134
5252794500
3397151474
44843260
15925043590
7615102649
642874296
805218390
12371730590
946262746
19013805530
1...

result:

ok 49918 numbers

Test #8:

score: 0
Accepted
time: 611ms
memory: 933436kb

input:

99992 100000
1 47419 74011 81562 83218
1 24365 27999 38558 68071
1 28685 99034 50336 45319
1 9957 51419 65767 96547
1 26613 48906 69394 57314
1 53501 94770 64814 21312
1 17181 66742 69740 22586
3 16409 7244 53001
1 88013 89718 83001 55044
1 37425 73824 89216 49784
1 14648 78441 67461 78275
1 9378 35...

output:

4417797626
26979560445
4524699650
21738613173
262351691
12978001923
17651184324
0
273579160
4411564116
1970670680
17453286633
14834332800
20575290994
10992737164
42531639041
7318986928
7239761756
24667868512
11295443456
33762100957
3516593780
14180850735
92220338161
448071480
72233196570
82174722698...

result:

ok 20053 numbers

Test #9:

score: 0
Accepted
time: 617ms
memory: 934844kb

input:

99993 100000
3 62344 1 1
1 46505 84554 62554 13482
1 8919 48492 3447 94458
1 3631 10892 36393 96414
1 2116 19576 2034 35286
1 76156 78230 41441 84879
1 36883 94127 37375 63171
1 39186 82305 6701 95798
3 78504 62801 72899
1 80076 91666 32526 7060
1 72382 96261 53068 10233
1 13914 57881 72281 7618
3 9...

output:

0
637963929
0
1496578500
10148463667
4717998934
125126442
10787190313
11490899784
2030671668
37797648
715325384
21191265941
3879816018
24364790835
25534294755
36504541523
6078290241
317915871
18538657312
22064935269
1065997831
3053544299
2695680279
55437334876
88991768121
1121205357
15153767807
5230...

result:

ok 20050 numbers

Test #10:

score: 0
Accepted
time: 555ms
memory: 420944kb

input:

99993 99996
3 38184 1 1
3 82734 1 1
1 25048 36616 78516 82979
3 95863 1 1
3 21933 1 1
3 49811 1 1
3 86826 1 1
3 94697 1 1
3 85109 1 1
3 40304 1 1
3 74963 1 1
3 21627 1 1
3 59714 1 1
3 87341 1 1
3 31090 15354 46066
1 38063 59594 70848 33527
3 32282 26788 77780
3 48817 25308 34737
3 58282 24515 41180
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
2548534027
4231348147
316159610
558760982
0
0
0
1166203168
1096131738
0
1103574732
299664326
11812262
0
0
0
147854070
78842610
60214492
331278844
0
0
3357828214
814586369
6914566022
603327305
0
0
515587541
244451179
0
560342272
2883490236
0
0
2965823280
29999739
511675577
2...

result:

ok 80045 numbers

Test #11:

score: 0
Accepted
time: 520ms
memory: 418184kb

input:

99999 99992
1 55982 96008 8771 41000
3 64884 827 1792
1 61684 84951 91560 74217
3 11864 1 1
3 73424 650 93216
1 45712 86024 18142 11742
3 69505 1599 109909
3 4215 1 1
3 70815 3258 82166
1 32918 86166 51184 24724
3 49468 10556 63376
3 11217 1 1
3 32460 1 1
3 58673 3861 11467
1 41409 47728 99526 31031...

output:

39606000
0
6600256565
7201866396
0
5673230715
1207451970
0
0
233007432
0
7603519685
4128358246
4817987659
0
4234154067
1579488960
70725000
0
243499000
1045745784
328164000
2552685084
209221360
114636000
139687000
1223600748
6074963562
1977843509
10990094062
220744000
36039000
243602384
3717973598
85...

result:

ok 80206 numbers

Test #12:

score: 0
Accepted
time: 197ms
memory: 384628kb

input:

100000 99993
1 47773 70467 16065 1
2 52349 78446 2304
3 40821 1 1
1 40216 93069 78144 1
1 41089 43671 76025 1
2 35263 68629 31066
3 79881 13534 57327
3 5556 1 1
2 21962 38192 1
1 664 58116 9417 1
3 28089 6039 7989
2 88500 90302 9946
3 63215 49410 60770
2 11069 89527 57581
2 70303 97603 12363
1 3420 ...

output:

0
43794
0
1951
11361
129
898
29245
7969
1947
34972
16405
59952
123666
24537
68209
34537
0
32225
37527
0
31810
16824
96178
14285
300941
57614
1602
129470
61935
4068
114182
17609
152949
26099
179359
250368
4796
183349
125791
17414
61871
42058
0
2698
183297
23029
54464
0
26259
204595
35604
0
0
18437
29...

result:

ok 33281 numbers

Test #13:

score: 0
Accepted
time: 218ms
memory: 381140kb

input:

100000 99999
3 11279 1 1
1 21196 82827 47041 1
2 58608 97529 1
2 22065 32528 37154
1 2138 16260 96858 1
1 25755 42875 82334 1
1 31799 48594 28327 1
3 58271 16371 33060
1 9407 50398 53680 1
2 40505 54132 176725
2 4626 22919 41250
2 28476 63110 133245
2 501 87564 1
2 5927 27401 96494
2 27254 64078 1
2...

output:

0
16690
27551
1442
4671
0
35160
4953
1559
3430
1768
0
0
11628
0
0
2495
13673
0
0
162093
135864
330
17312
0
29074
0
0
0
33641
51926
7051
0
0
42277
0
44110
543
12418
51322
9338
89794
9387
44052
43969
170272
42203
209676
5275
15969
11537
29757
26609
8288
33600
0
21384
48804
75598
11624
67508
10170
1751...

result:

ok 33467 numbers

Test #14:

score: 0
Accepted
time: 336ms
memory: 611924kb

input:

99993 99998
3 67041 1 1
3 6929 1 1
2 17524 32038 1
2 61604 73005 1
3 89616 1 1
2 40031 62338 1
3 58255 1 1
1 13009 67563 20939 1
1 73959 97229 47418 1
2 60834 61638 3740
2 29078 66369 1909
3 20355 4984 7284
2 75885 86625 3998
1 58692 90189 3242 1
3 99600 1 1
1 4102 8018 16478 1
3 53676 3918 8517
3 6...

output:

0
0
0
0
2301
0
4600
1472
56471
13213
0
143912
24988
0
59240
0
0
65385
5137
154745
70944
42704
209563
9676
121308
24627
52979
49278
37462
16444
0
1611
409040
392695
111628
265718
65783
55560
11142
45479
32621
118811
0
27594
239805
284844
19955
220309
8044
161759
1982
53200
41530
102413
43466
28624
17...

result:

ok 33389 numbers

Test #15:

score: 0
Accepted
time: 370ms
memory: 611100kb

input:

99991 99996
1 47657 83825 20467 1
2 18475 94316 1
1 45137 56194 42134 1
2 62287 64784 3656
1 34371 82222 66403 1
2 26982 76957 4461
2 1186 62584 1
2 63744 85641 5313
1 20658 59024 63800 1
2 51424 82606 5804
2 90768 91321 1
3 15951 1 1
2 51955 91548 1298
3 37870 8860 39509
3 8317 1 1
3 308 1 1
1 1977...

output:

0
30650
0
0
0
0
0
52497
2540
51822
0
22469
45077
10570
146261
11438
80060
21311
114935
197491
113332
156089
207620
36833
104730
21761
58044
72459
72699
105703
297859
98381
351013
75662
42544
50509
161825
375089
22703
209315
121760
4317
496943
121741
116864
11213
87742
871
452690
54302
100601
39830
2...

result:

ok 33262 numbers

Test #16:

score: 0
Accepted
time: 550ms
memory: 833444kb

input:

99997 99999
2 53252 91242 1
1 57337 88934 37260 1
1 16834 34642 93492 1
2 81166 94101 6093
1 46770 56947 41803 1
2 70882 88729 2179
2 55489 59818 1
1 29212 60579 61103 1
3 37904 1447 28743
1 68609 95313 51191 1
1 41758 51157 38733 1
3 57276 44404 49850
1 53448 66120 27464 1
1 64716 86889 8186 1
1 30...

output:

27297
5447
87454
7764
0
36668
9059
202784
226798
35791
44217
20176
425699
841344
314555
628121
279373
862035
1237442
638303
225509
1013325
143603
280017
469785
168019
102756
1008786
266597
5507
31097
1524290
288879
523157
706592
434088
1052960
282317
254606
633715
493060
281268
273353
139218
259977
...

result:

ok 16863 numbers

Test #17:

score: 0
Accepted
time: 205ms
memory: 386684kb

input:

99999 99996
3 77889 1 10000000000
1 6316 86327 89644 386
3 9260 1 10000000000
2 2603 47234 69717
2 20260 73011 19290
2 62477 81233 26127
1 50140 68508 37004 98794
2 14449 22788 16063
1 43860 84932 50375 21777
1 67345 94584 28202 66610
2 661 68654 1
1 14411 94422 82738 61196
1 16563 94416 4920 38408
...

output:

0
34602584
0
0
27739639583
1363823412
0
1902514434
1902514434
2147553884
1902514434
15794375094
0
4192446657
15797478185
13141921145
0
6351944090
5775183021
363222594
1995572111
2193350882
0
6843261316
5508935691
250667843
0
14181223499
7734049978
21958753162
12852564544
4496343819
15011219087
11331...

result:

ok 33196 numbers

Test #18:

score: 0
Accepted
time: 227ms
memory: 383872kb

input:

99993 100000
3 61460 1 10000000000
1 24890 92871 3803 26680
1 13860 37123 61687 5252
1 8370 24754 70468 14033
3 89253 1 10000000000
3 19857 1 10000000000
1 46250 80211 68621 64496
2 51133 69614 60852
1 6552 42728 61410 66775
3 16111 1 10000000000
3 48406 1 10000000000
2 46319 62460 3834
3 11455 1 10...

output:

0
101464040
1312857568
5413510318
4527244056
5089530194
4526096914
0
4475006240
7393292878
6354306906
5962661320
1073478334
14785061024
124598326
5273378126
3143834350
5315386486
567431731
3354264361
0
8452414800
16197376342
15594421332
7644906667
10259594309
15786872317
21575834611
25614641754
0
56...

result:

ok 33334 numbers

Test #19:

score: 0
Accepted
time: 401ms
memory: 609824kb

input:

99998 99996
3 40534 1 10000000000
1 89230 99016 8691 49307
1 73075 80610 27269 1760
1 80632 96125 13027 41376
1 55057 71990 82693 44377
2 11566 27301 1
2 23704 47061 1
1 67323 97867 14275 31136
1 11736 72566 78826 36301
3 70013 1 10000000000
1 23701 76122 6240 56626
2 71627 75885 1100
3 852 1 100000...

output:

0
6975596287
0
0
2144844585
6718561947
6718561947
2158130751
2917409114
3686398232
3317159253
1336852308
8373494196
2102154609
2709470190
1740124736
7659185913
1508488055
4242893725
8408091078
11875396012
18171183033
0
14595335642
18243076995
18521970659
18538979218
18538979218
20876408549
136521304...

result:

ok 33368 numbers

Test #20:

score: 0
Accepted
time: 387ms
memory: 612540kb

input:

99995 99996
3 45022 1 10000000000
2 3423 75909 1
1 54871 80611 9913 46243
2 12223 64484 1
1 12991 92385 39637 71608
3 20817 1 10000000000
3 14810 1 10000000000
3 85611 1 10000000000
3 34957 1 10000000000
3 22540 1 10000000000
2 11680 85376 4565
2 37283 97824 2191
3 84953 1 10000000000
3 56562 1 1000...

output:

0
2838326296
2838326296
2838326296
2838326296
2838326296
2354542648
2812903264
2631018944
2518569019
2681433168
2439582449
0
2681433168
2596475577
2439582449
0
7076261394
4449272647
15245942497
17667326760
15245942497
17667326760
17015058013
16860972874
42913399354
6034264601
96968820
12777724000
15...

result:

ok 33362 numbers

Test #21:

score: 0
Accepted
time: 509ms
memory: 828244kb

input:

99997 99996
3 68591 1 10000000000
2 11039 97222 1
1 34581 58556 66216 49214
1 42922 79247 32694 462
2 53032 58124 10301
3 34753 1 10000000000
1 22670 52566 70087 14019
3 55338 1 10000000000
3 30269 1 10000000000
1 4720 84384 20451 10356
3 11823 1 10000000000
1 37895 41892 96036 45498
2 19158 57043 7...

output:

0
3258754224
3269099790
982549653
211790556
1278106321
13591686831
9174283336
13929158983
10709860696
11476736634
24202776273
22066287959
23834159039
19695058244
28492871831
46736921586
859941225
5996946536
32463961710
31748786358
726580728
43724564767
39567498070
43724564767
57942980296
41944974287...

result:

ok 16689 numbers

Test #22:

score: 0
Accepted
time: 256ms
memory: 385600kb

input:

99992 99998
3 72033 1 1
3 44609 1 1
2 17104 74281 1
2 44893 69202 1
2 45964 95288 1
2 10378 32867 1
3 46668 1 1
1 47904 50614 6300 39627
3 77892 1 1
2 12074 16003 1
2 29299 73022 1
1 10163 90688 25621 55463
1 58567 85201 70361 35152
2 29333 47415 6701
1 45655 77719 14634 61416
1 12097 37093 88529 44...

output:

0
0
0
0
0
1734845091
964195228
0
0
0
888854492
9529234
2791503988
866833808
3838693368
5871819506
10104787629
5295548489
3189567114
3734880301
4351789494
435608352
0
251010938
0
0
380512558
504417673
215733075
6900751
149017616
2801426112
924476875
1839999945
0
255871875
3110328984
2251916667
525618...

result:

ok 33342 numbers

Test #23:

score: 0
Accepted
time: 206ms
memory: 385992kb

input:

99994 99999
3 42576 1 1
1 23088 66619 52799 39860
3 86524 1 1
1 11379 79818 17300 74251
2 43759 91424 1
1 16597 28868 30295 74271
2 28674 58996 66945
3 30208 1241 2541
2 16316 57261 1565
3 4540 1 1
3 5104 1 1
2 51314 85482 41249
2 40707 63006 1
2 3135 16258 1
2 3479 30844 1562
2 39173 88492 1
3 1596...

output:

0
0
51857860
0
0
0
0
0
5939140
5346066
1048656720
315566750
1603610304
447865074
0
0
0
174719157
0
1996596293
611019975
813361528
1580972816
3635411912
3179471802
0
0
864564689
4072449189
4935507212
2129476746
3426761505
3799411136
243783976
4682466849
6810330373
11762400
3141949961
3825928214
28050...

result:

ok 33174 numbers

Test #24:

score: 0
Accepted
time: 343ms
memory: 613336kb

input:

99990 99997
2 93596 96004 1
1 13319 34350 60754 66218
1 81405 99083 9343 71691
1 61275 62616 98317 80846
1 52894 77644 23380 92491
1 40321 77486 72440 97490
1 46113 60959 37629 68009
2 22890 69508 2972
1 49582 97276 32412 18314
1 15496 75607 11817 58054
2 14863 31978 5687
2 30568 69612 23186
1 3682 ...

output:

240716619
0
7425641926
3244358948
720126331
3175707237
2404493360
342055428
143382
219434787
592755306
2873215521
134377472
8967835337
475333908
294764346
448454918
613603269
1145956178
813995556
1490521853
437157744
7831144104
7088078663
406744932
1457390886
341828480
868640360
5946976613
517322568...

result:

ok 33078 numbers

Test #25:

score: 0
Accepted
time: 390ms
memory: 609380kb

input:

99993 99998
3 26198 1 1
3 11492 1 1
2 6627 76972 1
3 67936 1 1
2 64751 98500 1
1 30920 69769 37917 19590
2 54797 90136 1
2 8154 37524 1
3 87130 1 1
3 25965 1 1
3 57640 15242 31292
2 28028 41516 4714
3 2525 1 1
2 23998 36399 4671
1 74624 93138 24779 79965
1 92075 95396 32249 92242
2 75857 80407 2817
...

output:

0
0
0
0
0
314439090
0
1399387500
404151807
104834075
55459290
445564005
121797246
1890954291
22620264
5005171644
452287845
468534332
38190132
230502717
23527260
2802216556
171372096
3874994164
159932760
1832568192
3081169364
1449282670
4817731510
5624434648
3708911062
1409906122
1623944484
349747836...

result:

ok 33452 numbers

Test #26:

score: 0
Accepted
time: 467ms
memory: 832480kb

input:

99994 99992
1 57206 66519 28341 74797
3 56498 1 1
1 81303 86337 91447 58527
2 16687 63926 1
1 6458 52942 99861 33355
3 95579 1 1
2 69506 88501 1
3 35561 16645 46321
2 49047 84542 1
1 54826 58867 89571 98320
1 38387 92305 19384 76262
1 2729 26457 28979 95167
3 17582 56170 113246
1 8461 54127 51481 17...

output:

0
0
989876335
2731156955
565101420
0
1994488730
1684033447
5834977461
316041836
8870312086
1900896791
828800736
2356836268
6302743473
165143215
5752700000
4651468275
1112977455
12681686869
1216497856
8263259667
1808041130
6138571752
32066514305
13374139213
112765375
26708741051
26183221728
434074677...

result:

ok 16703 numbers

Extra Test:

score: 0
Extra Test Passed