QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785363#9638. 线段树与区间加zhouhuanyi100 ✓878ms83516kbC++173.4kb2024-11-26 17:39:412024-11-26 17:39:46

Judging History

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

  • [2024-11-26 17:39:46]
  • 评测
  • 测评结果:100
  • 用时:878ms
  • 内存:83516kb
  • [2024-11-26 17:39:41]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 400000
using namespace std;
unsigned int read()
{
	char c=0;
	unsigned int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct points
{
	int x,y;
	unsigned int data;
	bool operator < (const points &t)const
	{
		return x<t.x;
	}
};
int n,m,rt,sl[N+1],sr[N+1],ls[N+1],rs[N+1],fa[N+1];
unsigned int a[N+1],b[N+1],va[N+1],vb[N+1],delta[N+1],res;
void dfs(int x)
{
	vb[x]+=va[x]*(sr[x]-sl[x]+1);
	if (ls[x]) va[ls[x]]+=va[x],va[rs[x]]+=va[x],dfs(ls[x]),dfs(rs[x]);
	return;
}
bool cmp(points a,points b)
{
	return a.y<b.y;
}
struct KDT
{
	struct node
	{
		int x1,x2,y1,y2,ls,rs;
		unsigned int data,res,lazy2;
		bool lazy;
	};
	node tree[(N<<2)+1];
	int length;
	void push_up(int k)
	{
		tree[k].res=tree[tree[k].ls].res+tree[tree[k].rs].res;
		return;
	}
	void push_tag(int k)
	{
		tree[k].res=tree[k].lazy2=0,tree[k].lazy=1;
		return;
	}
	void push_tag2(int k,unsigned int d)
	{
		tree[k].res+=tree[k].data*d,tree[k].lazy2+=d;
		return;
	}
	void spread(int k)
    {
		if (tree[k].lazy) push_tag(tree[k].ls),push_tag(tree[k].rs),tree[k].lazy=0;
		if (tree[k].lazy2) push_tag2(tree[k].ls,tree[k].lazy2),push_tag2(tree[k].rs,tree[k].lazy2),tree[k].lazy2=0;
		return;
	}
	int build(vector<points>p)
	{
	    int nw=++length;
		vector<points>A;
		vector<points>B;
		tree[nw].x1=tree[nw].x2=p[0].x,tree[nw].y1=tree[nw].y2=p[0].y,tree[nw].data=p[0].data;
		for (int i=1;i<p.size();++i) tree[nw].x1=min(tree[nw].x1,p[i].x),tree[nw].x2=max(tree[nw].x2,p[i].x),tree[nw].y1=min(tree[nw].y1,p[i].y),tree[nw].y2=max(tree[nw].y2,p[i].y),tree[nw].data+=p[i].data;
		if (p.size()==1) return nw;
		if (tree[nw].x2-tree[nw].x1>=tree[nw].y2-tree[nw].y1) nth_element(p.begin(),p.begin()+(p.size()>>1),p.end());
		else nth_element(p.begin(),p.begin()+(p.size()>>1),p.end(),cmp);
		for (int i=0;i<(p.size()>>1);++i) A.push_back(p[i]);
		for (int i=(p.size()>>1);i<p.size();++i) B.push_back(p[i]);
		tree[nw].ls=build(A),tree[nw].rs=build(B);
		return nw;
	}
	void add(int k,int l1,int r1,int l2,int r2,unsigned int d)
	{
		if (max(tree[k].x1,l1)>min(tree[k].x2,r1)||max(tree[k].y1,l2)>min(tree[k].y2,r2)) return;
		if (l1<=tree[k].x1&&tree[k].x2<=r1&&l2<=tree[k].y1&&tree[k].y2<=r2)
		{
			push_tag2(k,d);
			return;
		}
		spread(k),add(tree[k].ls,l1,r1,l2,r2,d),add(tree[k].rs,l1,r1,l2,r2,d),push_up(k);
		return;
	}
	void clear(int k,int l1,int r1,int l2,int r2)
	{
		if (max(tree[k].x1,l1)>min(tree[k].x2,r1)||max(tree[k].y1,l2)>min(tree[k].y2,r2)) return;
		if (l1<=tree[k].x1&&tree[k].x2<=r1&&l2<=tree[k].y1&&tree[k].y2<=r2)
		{
			push_tag(k);
			return;
		}
		spread(k),clear(tree[k].ls,l1,r1,l2,r2),clear(tree[k].rs,l1,r1,l2,r2),push_up(k);
		return;
	}
};
KDT T;
int main()
{
	vector<points>p;
	int l,r,d;
	n=read(),m=read();
	for (int i=1;i<=(n<<1)-1;++i)
	{
		sl[i]=read(),sr[i]=read(),va[i]=read(),vb[i]=read();
		if (sl[i]!=sr[i]) ls[i]=read(),rs[i]=read(),fa[ls[i]]=fa[rs[i]]=i;
		if (sl[i]==1&&sr[i]==n) rt=i;
	}
	dfs(rt);
	for (int i=1;i<=(n<<1)-1;++i)
	{
		if (fa[i]) delta[fa[i]]-=vb[i];
		delta[i]+=vb[i];
	}
	for (int i=1;i<=(n<<1)-1;++i) p.push_back((points){sl[i],sr[i],delta[i]});
	rt=T.build(p);
	while (m--) l=read(),r=read(),d=read(),T.clear(rt,1,l-1,l,n),T.clear(rt,1,r,r+1,n),T.add(rt,l,r,l,r,d),printf("%u\n",T.tree[rt].res);
	return 0;
}

详细


Pretests


Final Tests

Test #1:

score: 4
Accepted
time: 7ms
memory: 18924kb

input:

2000 2000
1793 1798 1262660447 3355636366 3629 1228
103 1852 1180930258 1265499397 1821 3806
680 680 2673755170 3193571303
737 740 3064103572 3343535318 1993 502
1720 1721 3117882744 1227116751 3561 1857
117 117 2249090646 234980450
1897 1901 87845907 4069299503 2523 1140
1832 1835 981230847 3022191...

output:

3152111116
2269465037
1020991279
2060980533
1885995758
417076086
736747214
2513959201
3184324885
3697138385
662770561
401858861
1274318719
1020329762
768736209
2287731317
450918148
2232046661
1320372894
411387185
1145249743
1944516793
3601186359
3177833216
3363894235
1653459287
3591709536
3536881616...

result:

ok 2000 lines

Test #2:

score: 4
Accepted
time: 4ms
memory: 18720kb

input:

2000 2000
372 372 0 989361745
268 744 0 2134086804 3992 1151
929 932 0 3450655381 1108 1775
1527 1527 0 2098122263
261 264 0 767043297 3813 2562
1011 1013 0 1426875762 997 1431
160 160 0 2574808476
1660 1770 0 2181120880 1536 69
1650 1650 0 3634539115
811 811 0 4269292508
518 518 0 3874323908
248 25...

output:

2047726267
829839247
2463999625
496324019
4209639157
2623761375
1359068079
3809469447
2444726435
1544210716
3362325969
3918469522
3152929153
941944849
358312207
1181369011
718509632
4225129031
1846368072
2272699224
2486755452
2134599722
2814440447
2530755991
978331171
3294812397
2592160816
408417118...

result:

ok 2000 lines

Test #3:

score: 4
Accepted
time: 3ms
memory: 20452kb

input:

2000 2000
1045 1046 0 2632377141 2540 3747
1673 1674 0 1669064774 1585 1359
1737 1737 0 4187517691
134 134 0 1381105987
1678 1678 0 3194199856
629 632 0 1039365507 1669 3337
1224 1225 0 2056342816 2564 1715
501 1491 0 2746594998 563 3172
1859 1860 0 1399867507 3486 1239
377 377 0 4114286174
266 266 ...

output:

1036900736
3610864420
2683773728
897731888
184069192
3882244294
4253560882
551966036
2397168713
2270590828
1804704604
2579256374
3374484230
1168411590
3513258279
3004975727
274143781
2752343114
158802831
1853548649
3893149476
2199946557
1251789344
1946730546
3196311838
4036266023
57082068
3387529954...

result:

ok 2000 lines

Test #4:

score: 4
Accepted
time: 4ms
memory: 18896kb

input:

2000 2000
1922 1923 4154142567 0 624 1116
1611 1625 1842722647 0 1405 1312
101 102 328256453 0 3110 2786
859 860 1546215739 0 489 2099
1154 1157 4134074442 0 341 792
531 532 1656285477 0 1961 1533
451 454 2149232978 0 3570 253
496 496 12489066 0
1697 1700 2769881303 0 2485 3845
1232 1232 4274380990 ...

output:

1244935696
3881730871
3861620299
3630808070
143145097
2542509128
1911111576
1280561467
1684782375
2123438102
2161767784
3868604371
1741793529
2089766304
678790465
1362988883
4274049504
2200807299
860968345
3853101004
3567112617
324269778
1482245920
1786084156
4221544804
1782731166
734908652
43686813...

result:

ok 2000 lines

Test #5:

score: 4
Accepted
time: 7ms
memory: 18652kb

input:

2000 2000
1516 1516 786840671 0
546 547 533550872 0 3506 319
947 952 3586638444 0 1398 2922
1769 1777 1598495528 0 2351 3492
1487 1488 3433976236 0 2998 372
266 268 4081199540 0 3034 1376
9 11 16162852 0 2016 2453
606 606 868772445 0
500 501 1406522390 0 1201 3967
1448 1449 2080781326 0 1547 1988
22...

output:

355422488
3256264388
2788279524
918980988
2210590456
3507874393
505332537
3048538642
4064960139
1074955896
3262754244
36045922
102158252
2531234752
2688363642
3901653384
1506351899
3058812581
1455338180
3078090178
3231337104
1798127493
3384246559
3744336983
2892296332
2097334835
441826825
2362367029...

result:

ok 2000 lines

Test #6:

score: 4
Accepted
time: 157ms
memory: 28692kb

input:

40000 40000
19061 19064 2717945240 3834098532 59850 71996
14933 14933 877340266 1841904212
34098 34170 3550522541 2738188651 75607 2753
4691 4691 530532762 675854163
9890 9890 2833834223 2233457146
14140 14140 1300081732 193421532
1623 1623 1598527863 3121134528
4929 4929 1218079042 439770536
324 39...

output:

3762372552
3207760904
3619039300
4092427780
2231095264
3484986624
3118686528
1669200743
1156800853
522443062
571921897
4148653608
2526624875
3008302129
2382936909
2416988785
3120827544
1059270642
1386980750
252426796
1142511302
2311815351
3780381011
2528441172
491780027
2579209293
3656132546
3096172...

result:

ok 40000 lines

Test #7:

score: 4
Accepted
time: 127ms
memory: 28440kb

input:

40000 40000
37504 37504 0 2993769426
14320 14322 0 3704545631 44050 52152
2757 37130 0 1236105917 2455 3677
884 884 0 4026492894
10076 10077 0 609448457 7650 75701
16404 16404 0 245461674
22018 22018 0 2771692605
1501 1501 0 2419888954
16860 16861 0 1871411848 33204 21442
15067 15068 0 1175031405 20...

output:

2153180388
3760226490
3157170422
437843217
2769574737
1780766937
3636948769
2918666029
4053304121
2426843089
42110371
2805622851
2426086057
3124096482
1440737801
3409308631
1399767957
3420242340
3695049174
1307316093
3649944812
3010322189
452747957
1858015508
3254134541
1199974266
1326428787
3438928...

result:

ok 40000 lines

Test #8:

score: 4
Accepted
time: 118ms
memory: 31740kb

input:

40000 40000
20206 20206 0 4103926985
25572 25573 0 1124285259 79417 25683
23524 23524 0 2945938453
26314 26316 0 3769707656 62994 20223
1933 1933 0 3202000408
12690 27072 0 663839624 50239 60259
27007 27013 0 1608124753 48394 32123
1283 1284 0 4010999538 17252 36084
11373 11375 0 3200987115 25973 22...

output:

287427596
3686765151
68417240
3015310130
2985080231
2348131493
1757151821
2179625358
79672615
2755221531
1432895979
3929722253
2726545650
3855501322
986830777
1435872122
2161738920
4160516876
1401789628
3329392576
2280597011
4146608571
110783231
1972852168
1359374849
3143963964
1211191548
2440558924...

result:

ok 40000 lines

Test #9:

score: 4
Accepted
time: 127ms
memory: 28992kb

input:

40000 40000
28600 31103 398400104 0 50206 67695
18214 18214 987691543 0
21117 21117 2501164446 0
35971 35972 884844107 0 49942 386
17501 17501 4216208706 0
12649 12649 3198897355 0
1690 1695 1689582721 0 30803 36361
33084 33084 2651714130 0
26656 26660 3389387136 0 27495 17328
32764 32764 2921506964...

output:

2661989864
1947893360
2177273740
2805317845
3770448246
2061736392
1286068422
632882163
3718808793
1339549657
1307728358
1283051688
2714825475
994135893
4142896407
4091591129
445121640
2810682714
1807820506
2543434294
2527190896
1674553699
2254191164
2154047668
2209081836
465070118
4118239274
2112220...

result:

ok 40000 lines

Test #10:

score: 4
Accepted
time: 138ms
memory: 28564kb

input:

40000 40000
24203 24203 1353036479 0
30073 30082 1740596718 0 53750 62241
11650 11652 3664808690 0 7271 53525
17686 17686 2170088447 0
14215 14215 877899577 0
10389 14544 1220290260 0 2779 34931
17557 17561 3312844542 0 9486 56774
37025 37026 360931058 0 52630 1863
8544 8545 2355582057 0 34372 13606...

output:

2519124594
2634462594
1417233555
3471878224
3842866513
3184281095
2935202671
521564492
3416348650
162479576
3589724768
212609364
71379846
2070355303
3565115141
3837902349
3818069677
1727479892
3949071907
1303465618
1184109510
1311402470
1395756280
3730263576
113268436
886996392
3630256423
3074325479...

result:

ok 40000 lines

Test #11:

score: 4
Accepted
time: 719ms
memory: 80828kb

input:

200000 200000
32600 32601 279707947 3333652085 81223 369345
107195 110357 2797643167 3204100200 211635 180774
50076 50076 3586231592 2031356328
9086 9086 2226760698 457985624
89785 143170 2137446218 370802330 339432 56185
15190 19580 3336566407 2687475581 239505 274514
199717 199717 1343907462 27476...

output:

2009836216
3727996800
3450134793
3406485732
1123726936
1170973510
764967399
1336588779
917647199
2249365950
2934805008
1625886692
2425348432
3997654416
3288567872
3719461083
228163419
1349877510
2715061693
3905289161
813191337
1445005585
1078905575
3999781666
3626536053
3480952270
1200888304
7849245...

result:

ok 200000 lines

Test #12:

score: 4
Accepted
time: 662ms
memory: 82756kb

input:

200000 200000
103447 103448 0 2671179003 304649 129499
145911 145911 0 1121422691
157741 157744 0 1929193038 145603 72009
11904 11905 0 2289998670 146636 237088
122867 122868 0 186090819 413 270761
193873 193873 0 203093844
20838 20838 0 2999266101
92497 92498 0 2375994881 321423 197661
10185 10185 ...

output:

1287630144
1911410702
2542412142
2949149180
2597050152
1479226049
699517062
1840378744
3561042026
2295091954
1476949713
318057754
3160099934
2529106282
1409773717
2979058284
254069790
2408520951
767089333
2745981939
2707418577
350113395
2245460988
2655942395
3685437519
3972634965
351126485
128739571...

result:

ok 200000 lines

Test #13:

score: 4
Accepted
time: 604ms
memory: 79516kb

input:

200000 200000
190183 190188 0 1706040846 362170 41622
150705 150705 0 2188179441
148325 148330 0 2355075143 61581 324431
190406 190407 0 1131747042 383315 217073
23144 23152 0 1897327529 396050 285637
93051 93051 0 1804212175
186538 186541 0 3315936642 306793 151829
45692 45692 0 1239029798
30972 30...

output:

2075029659
3550857507
3975089737
1922279342
534671262
1315305932
3932082574
576645640
1491251464
1599102206
2909848918
2484431669
2562655797
1342243997
95469720
3085411021
4220881397
2707863723
509188519
2382632511
2493078850
3595217833
1848800013
4146508855
3672985783
880937040
2586434528
940969940...

result:

ok 200000 lines

Test #14:

score: 4
Accepted
time: 626ms
memory: 80116kb

input:

200000 200000
90506 102530 236918570 0 337847 201999
50479 50482 1884914043 0 242965 18370
197965 197965 1150415084 0
181841 181841 524351831 0
43868 43886 3739237894 0 365544 340081
104279 104279 1518148351 0
34148 34154 3970381744 0 379789 218872
73698 73698 3847658012 0
71224 71225 2029945887 0 3...

output:

2255959540
776843588
1939762368
407450021
2416728973
3351051967
238272039
3173214263
964780820
2479009385
2078308329
1085718897
3336408401
2469655047
3702885352
590105323
625121410
2752075115
3402348887
2538671649
3018668433
680197831
421512740
52919903
1904990371
2601865274
2699800194
868148810
207...

result:

ok 200000 lines

Test #15:

score: 4
Accepted
time: 675ms
memory: 82744kb

input:

200000 200000
184636 184636 470383782 0
69147 163622 581509052 0 286341 357499
95155 95155 577954429 0
126294 126294 3693354981 0
184618 187568 3886149811 0 333358 166507
188512 188512 303047117 0
20400 20400 3407789462 0
44704 44705 1224895264 0 162096 75280
133755 133757 109227272 0 132577 372294
...

output:

3881118135
3222757985
114387977
2262724873
1481024296
3192177672
1825099959
3248957793
800918233
2409713038
1720265294
846986202
3604862840
2795825247
2843485417
302001729
4214926529
1468759477
2241022395
1641387459
929124036
182926454
8909911
3676263238
36476901
4207789233
2593381466
1110673084
829...

result:

ok 200000 lines

Test #16:

score: 4
Accepted
time: 822ms
memory: 83200kb

input:

200000 200000
30492 35854 729190907 1956530869 220290 207964
178288 178288 793919639 4043397768
4965 4965 2255872372 819681301
64878 99465 669086428 517288923 75560 27338
13595 16760 415742798 3804064469 203533 253759
154291 154293 601666143 200879632 289484 190128
121100 121101 2476950350 105407364...

output:

3408975650
1260373822
2094643123
170444138
914907647
2434503559
563533321
2084423797
2795129313
2120903359
2101179239
901911043
1777694453
1308222834
2182085500
1040269104
459263554
1460300386
982590159
2446643586
3610631483
3871148413
4174679155
403601560
193602219
1968824607
1825526007
1145265521
...

result:

ok 200000 lines

Test #17:

score: 4
Accepted
time: 815ms
memory: 81124kb

input:

200000 200000
158994 158994 0 2397655320
165026 165026 0 1247467790
193088 193089 0 1131792894 25325 134960
34834 34834 0 1974874050
106908 106908 0 158855686
73570 73571 0 660499851 32725 33730
126276 126276 0 2799927501
183868 183870 0 2792433045 319704 248051
145831 145832 0 796369972 384435 1211...

output:

3513723604
2754715804
1528311189
2257520181
2721970092
815029065
703984582
1545028831
314736545
1411651251
2539744056
974143421
738089030
4087093402
155631567
2768665008
2337487423
3222624969
1982097006
3340343695
3561777503
3429164481
270495708
284453578
3328913072
3855066732
1076856283
4079411614
...

result:

ok 200000 lines

Test #18:

score: 4
Accepted
time: 843ms
memory: 81148kb

input:

200000 200000
42026 42026 0 103840682
115527 115527 0 730801603
175286 175286 0 952465904
115721 115722 0 3887082779 210578 202527
14017 17027 0 2717984672 155430 298216
113340 113340 0 1196664755
143222 143224 0 1622284707 237907 258953
115973 115975 0 2441078898 207848 192004
54478 54478 0 3169258...

output:

2991484163
2272442507
3439612306
621121047
4189594876
737060417
4239264766
1261151974
4083144803
1922155292
3647076642
4200711525
79778695
1284474703
4236218542
1778029637
2230695170
1353980579
4257512162
2826953793
1080665359
3242252014
4137520954
849182125
3587368991
1483093554
4242582131
42854999...

result:

ok 200000 lines

Test #19:

score: 4
Accepted
time: 876ms
memory: 81744kb

input:

200000 200000
92524 92524 182603024 0
116778 116778 2576939405 0
10207 10207 1898802503 0
178036 178038 1935186518 0 44870 317892
137541 137544 2674676024 0 210860 64999
68085 68085 1958593201 0
179926 179929 2584382023 0 185913 349215
45422 45423 2495993608 0 157833 264143
109854 121340 113104103 0...

output:

2492113792
387547552
1287637345
1246110835
3554600264
2475459858
817374010
860956968
3592212748
843429959
892269148
2605540021
1936900198
3444541631
897088597
2122584008
3776561361
2718574796
4068742267
2171824493
3882117424
2986652517
3044629662
1506524729
1709279996
1909679383
476604845
3231501778...

result:

ok 200000 lines

Test #20:

score: 4
Accepted
time: 725ms
memory: 81904kb

input:

200000 200000
12387 12389 2109068107 0 384829 227596
26592 26594 2550267931 0 57077 72658
80444 80444 1329109323 0
119995 119995 4165698375 0
48876 48876 766047886 0
155836 155836 3512049107 0
50100 50100 1831955483 0
193088 193089 3589455426 0 34273 140648
126549 126549 1726763169 0
149430 154350 1...

output:

569029630
311635424
3739584698
359129174
1753297532
1305935475
1374589943
3464547062
2330850518
1484796394
2114090757
1901682195
1305826277
673509997
2742098365
4035655271
433281375
3757714729
3033297819
178695315
2478541628
862382819
3146110952
2738114560
1833832974
2981667281
1263472846
486182013
...

result:

ok 200000 lines

Test #21:

score: 4
Accepted
time: 878ms
memory: 80300kb

input:

200000 200000
165129 165131 3633865218 98447901 160942 69260
170590 170592 2878276602 4164208122 147121 65383
199006 199017 3624152661 4138881358 49640 64235
92616 137590 1278705205 1262535969 229078 92015
12733 12733 1753647128 400573041
138294 138294 503689729 1701121075
178554 185671 951413620 10...

output:

2335307688
2405142840
4136486082
4270755027
2477554787
3476497519
991638607
154584536
2994033096
264554588
1974982474
2874515180
1199831924
4182570682
79356654
1522687005
2505213951
311612137
3772839283
3633650165
4222273737
2740057083
1350580457
3413616536
2947909190
1888737313
294131163
3963507580...

result:

ok 200000 lines

Test #22:

score: 4
Accepted
time: 773ms
memory: 83516kb

input:

200000 200000
42616 42616 0 4073548647
148817 148819 0 678516345 137141 295278
136568 136568 0 1311526245
162591 162591 0 1123778942
152429 152430 0 865424725 274628 226053
123226 123226 0 1843160929
3315 3315 0 2548140955
158521 158522 0 726899994 308692 139695
128630 128630 0 3560425273
137094 137...

output:

1344432873
1342029107
529243785
2996912847
3100214932
543839524
881029487
374973159
2844125553
1474904439
4084570059
1811100787
3382401205
1294703480
571801327
2450526145
1529905375
3186330149
1645547964
2241430385
3731680977
390502197
2288256789
2156725625
3395831846
690635289
3657387709
3036878023...

result:

ok 200000 lines

Test #23:

score: 4
Accepted
time: 777ms
memory: 81400kb

input:

200000 200000
92930 92933 0 945338790 270177 344831
44586 44586 0 2120126372
80169 80169 0 3407810035
173606 173606 0 2056188474
144888 144888 0 1376882346
9586 9586 0 2496173660
67542 67542 0 3278572994
95705 95705 0 2103944675
73814 73815 0 4244900263 66623 87248
149429 149431 0 2014898776 8786 61...

output:

2400628999
3889329248
3526331118
2817930844
4172414439
3948498757
280840676
2467121446
2638008618
3317006669
1612243920
3351117731
1187114458
1860822434
3105027092
3023823335
4195517641
2380370511
2391156451
2039675702
2787175557
1612701131
3847086798
2598623872
2957738558
1124705980
4284401663
3479...

result:

ok 200000 lines

Test #24:

score: 4
Accepted
time: 786ms
memory: 82952kb

input:

200000 200000
182457 182458 3070241886 0 235330 232917
130450 160512 2343593919 0 288610 262204
86835 86836 2084902783 0 271317 299422
39111 91715 827843559 0 14965 357810
131676 131677 2889067161 0 266237 6055
88274 88274 4216568292 0
119859 119861 3636500316 0 297047 394521
30700 112091 528067902 ...

output:

232843874
3859588364
4061971686
3229697766
768722138
3628079555
1171480643
2327135560
3076854411
3090084018
768799705
3410231241
1345078640
3430977197
143599789
2278623575
2946691797
984916925
4081086279
134265600
803886895
3598885394
1931230981
2897966763
935493305
2972270338
1451927266
1041356600
...

result:

ok 200000 lines

Test #25:

score: 4
Accepted
time: 754ms
memory: 81516kb

input:

200000 200000
16728 16728 2942007300 0
176509 176509 1919353043 0
102679 102679 3974389408 0
182519 182519 1184106257 0
83079 83089 1520374942 0 181757 4901
35926 35926 2259226600 0
33932 33933 3693656209 0 101981 2261
1804 1805 4038337356 0 92067 46297
15141 15143 4117148560 0 172165 356831
59008 5...

output:

1004805744
1590024402
3730693826
1559294237
1731869573
3120634605
3849899635
2263931148
1149785468
1275293204
1183074874
2186222154
3663082834
3028177459
3058881381
17465701
1454709892
4135314630
3940212968
2005209
1553786931
171494779
4004835088
2442859104
3959824050
4289605916
2346822689
340108913...

result:

ok 200000 lines