QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440673#8522. Waterfall Matrixucup-team3586#TL 5298ms42896kbC++234.4kb2024-06-13 22:34:342024-06-13 22:34:36

Judging History

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

  • [2024-06-13 22:34:36]
  • 评测
  • 测评结果:TL
  • 用时:5298ms
  • 内存:42896kb
  • [2024-06-13 22:34:34]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define ls (x<<1)
#define rs (ls|1)
void die(string S){puts(S.c_str());exit(0);}
int n,a[200200],b[200200],c[200200],ans[200200];
vector<int> poolx,pooly;
vector<pii> vy[200200];
// vector<pii> helper[200200];
int xx[200200],yy[200200];
pii *helper[200200];
int Pos[200200];
int tag[200200<<2],tagmx[200200<<2],mx[200200<<2],mxpos[200200<<2];
void build(int x,int l,int r)
{
	tag[x]=mx[x]=0;
	tagmx[x]=-inf;
	mxpos[x]=l;
	if(l==r) return ;
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void pushdown(int x,int l,int r)
{
	if(!tag[x]&&tagmx[x]<-1e6) return ;
	mx[x]=max(mx[x]+tag[x],tagmx[x]);
	if(l!=r)
	{
		tag[ls]+=tag[x];
		tag[rs]+=tag[x];
		tagmx[ls]=max(tagmx[ls]+tag[x],tagmx[x]);
		tagmx[rs]=max(tagmx[rs]+tag[x],tagmx[x]);
	}
	tag[x]=0;
	tagmx[x]=-inf;
}
void pushup(int x,int l,int r)
{
	int mid=(l+r)/2;
	pushdown(ls,l,mid);
	pushdown(rs,mid+1,r);
	mx[x]=max(mx[ls],mx[rs]);
	if(mx[ls]==mx[x])
		mxpos[x]=mxpos[ls];
	else
		mxpos[x]=mxpos[rs];
}
void add(int x,int l,int r,int ql,int qr,int v)
{
	pushdown(x,l,r);
	if(ql<=l&&r<=qr)
	{
		tag[x]+=v;
		tagmx[x]+=v;
		return ;
	}
	int mid=(l+r)/2;
	if(ql<=mid)
		add(ls,l,mid,ql,qr,v);
	if(qr>mid)
		add(rs,mid+1,r,ql,qr,v);
	pushup(x,l,r);
}
void setmx(int x,int l,int r,int ql,int qr,int v)
{
	pushdown(x,l,r);
	if(ql<=l&&r<=qr)
	{
		tagmx[x]=max(tagmx[x],v);
		return ;
	}
	int mid=(l+r)/2;
	if(ql<=mid)
		setmx(ls,l,mid,ql,qr,v);
	if(qr>mid)
		setmx(rs,mid+1,r,ql,qr,v);
	pushup(x,l,r);
}
pii query(int x,int l,int r,int ql,int qr)
{
	pushdown(x,l,r);
	if(l==ql&&r==qr)
		return mp(mx[x],mxpos[x]);
	int mid=(l+r)/2;
	if(qr<=mid) return query(ls,l,mid,ql,qr);
	if(ql>mid) return query(rs,mid+1,r,ql,qr);
	return max(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
}
void solve(vector<int> &vec,int L,int R)
{
	if(!sz(vec)) return ;
	if(L==R)
	{
		for(auto x:vec)
			ans[x]=L;
		return ;
	}
	int mid=(L+R)/2;
	poolx.clear();
	pooly.clear();
	for(auto ind:vec)
		poolx.pb(a[ind]);
	for(auto ind:vec)
		pooly.pb(b[ind]);
	srt(poolx);
	uni(poolx);
	srt(pooly);
	uni(pooly);
	int N=sz(poolx),M=sz(pooly);
	for(int i=0;i<=N;i++)
	{
		vy[i].clear();
		// helper[i].clear();
	}
	for(auto ind:vec)
	{
		int x=xx[ind]=ub(poolx,a[ind]);
		vy[x].pb(yy[ind]=ub(pooly,b[ind]),(c[ind]>mid?1:0));
	}
	for(int i=0;i<=N;i++)
		srt(vy[i]);
	build(1,1,M+1);
	for(int i=1;i<=N;i++)
	{
		static int vpos[1<<20];
		int sz=0;
		for(auto pr:vy[i])
			add(1,1,M+1,1,pr.first,(pr.second?-1:1));
		// vector<int> vpos;
		// vpos.pb(0);
		vpos[sz++]=0;
		for(auto pr:vy[i])
			vpos[sz++]=pr.first;
			// vpos.pb(pr.first);
		// vpos.pb(M+1);
		vpos[sz++]=M+1;
		// helper[i].resize(sz(vy[i])+1);
		delete helper[i];
		helper[i]=new pii[sz(vy[i])+1];
		pii cur=mp(-inf,-inf);
		for(int j=sz-1;j;j--)
		{
			helper[i][j-1]=cur;
			setmx(1,1,M+1,vpos[j-1]+1,vpos[j],cur.first);
			cur=max(query(1,1,M+1,vpos[j-1]+1,vpos[j]),cur);
		}
	}
	pii pr=query(1,1,M+1,1,M+1);
	int val=pr.first,pos=pr.second;
	for(int i=N;i>=1;i--)
	{
		int label=0;
		while(label<sz(vy[i])&&vy[i][label].first<pos)
			label++;
		if(val==helper[i][label].first)
			pos=helper[i][label].second;
		Pos[i]=pos;
		for(auto pr:vy[i])
			if(pos<=pr.first)
				val+=(pr.second?1:-1);
	}
	vector<int> V1,V2;
	for(auto ind:vec)
	{
		int x=xx[ind];
		int y=yy[ind];
		if(y>=Pos[x])
			V1.pb(ind);
		else
			V2.pb(ind);
	}
	solve(V1,L,mid);
	solve(V2,mid+1,R);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i]>>c[i];
	vector<int> vec;
	for(int i=1;i<=n;i++)
		vec.pb(i);
	solve(vec,1,1000000000);
	ll ans=0;
	for(int i=1;i<=n;i++)
		ans+=abs(::ans[i]-c[i]);
	cout<<ans<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 18136kb

input:

5
1 3 5
3 2 1
3 3 3
4 4 1
3 5 4

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 17968kb

input:

1
1 1 58383964

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 3ms
memory: 15916kb

input:

2
1 1 204909414
2 2 807091086

output:

602181672

result:

ok 1 number(s): "602181672"

Test #4:

score: 0
Accepted
time: 3ms
memory: 17960kb

input:

4
2 4 107744934
3 2 143843719
4 4 908851567
2 2 307161330

output:

801106633

result:

ok 1 number(s): "801106633"

Test #5:

score: 0
Accepted
time: 0ms
memory: 18116kb

input:

7
1 2 140766572
5 3 795389698
3 6 279722536
2 6 442413348
4 2 475716910
5 4 704493410
5 2 423494885

output:

935621651

result:

ok 1 number(s): "935621651"

Test #6:

score: 0
Accepted
time: 3ms
memory: 15908kb

input:

11
1 5 104443431
4 9 692130290
4 1 18812720
7 3 381505729
7 7 706418558
11 9 242808397
10 4 490383412
3 2 72839501
10 7 883914647
10 6 738589165
11 10 556539693

output:

2757182575

result:

ok 1 number(s): "2757182575"

Test #7:

score: 0
Accepted
time: 0ms
memory: 15864kb

input:

17
14 13 957289906
14 1 220840920
10 3 230060608
9 12 405076666
13 5 112827045
12 12 925699151
11 9 243364659
3 15 66125969
1 5 481618704
17 11 67207393
9 4 141885319
2 2 641760683
4 6 30421350
5 9 145177348
7 13 468875688
11 7 557989385
13 17 468110036

output:

3056543193

result:

ok 1 number(s): "3056543193"

Test #8:

score: 0
Accepted
time: 0ms
memory: 15828kb

input:

26
22 1 655039096
18 3 405980640
11 23 310084709
17 6 5210226
6 25 869210460
14 23 9079903
17 9 162692938
21 1 703337421
13 8 216969244
8 23 242760842
11 9 876472951
5 15 545320494
8 6 764694540
4 12 164086724
6 13 394175551
10 1 906738317
26 25 224731347
12 14 967318812
26 14 449256484
23 4 6152281...

output:

3872286425

result:

ok 1 number(s): "3872286425"

Test #9:

score: 0
Accepted
time: 0ms
memory: 15840kb

input:

40
33 19 974202889
40 11 262863105
18 17 143706322
15 37 253303786
4 8 962133788
40 22 885916470
22 19 949122323
32 29 221627390
17 24 605257795
3 14 259799950
5 3 987951246
28 30 451968921
13 17 503334855
11 26 190979064
11 13 497711531
29 4 764544900
38 16 199461325
7 9 618831071
25 30 209848351
1...

output:

7657769074

result:

ok 1 number(s): "7657769074"

Test #10:

score: 0
Accepted
time: 0ms
memory: 17896kb

input:

61
6 25 772410634
9 47 581631393
40 34 565465748
8 55 154525415
3 50 298013089
16 23 593130934
26 5 721815207
42 43 28712243
61 21 539501497
49 53 283028482
4 20 267467572
59 45 55599983
26 3 218043086
15 8 213292621
37 44 119318590
29 33 445273185
37 3 734748198
21 56 178476345
12 40 897802983
3 29...

output:

9305689053

result:

ok 1 number(s): "9305689053"

Test #11:

score: 0
Accepted
time: 0ms
memory: 15876kb

input:

92
67 63 115551817
40 57 922062274
21 83 268857323
59 65 957783695
44 1 720871230
44 65 682393003
85 21 850933251
47 32 990892557
75 90 807656030
37 83 446279042
6 8 121301986
52 34 648749799
29 56 519610045
58 28 915936953
19 8 736754508
77 25 251573087
77 5 708764858
71 66 395892865
37 9 339525762...

output:

20584500053

result:

ok 1 number(s): "20584500053"

Test #12:

score: 0
Accepted
time: 0ms
memory: 17908kb

input:

139
34 89 106739274
76 37 623575790
96 95 241595468
100 37 24819785
67 78 157943133
86 66 173514198
6 107 220712008
95 94 902234730
124 117 827871287
82 10 199132415
48 29 821720496
99 15 21336498
79 84 287004315
27 57 112113016
102 106 99696275
52 94 326387056
17 41 717541828
24 119 561086579
137 1...

output:

34223480997

result:

ok 1 number(s): "34223480997"

Test #13:

score: 0
Accepted
time: 5ms
memory: 15976kb

input:

209
202 11 985436507
81 23 303372005
58 65 271936110
105 6 780231383
183 131 67052291
140 15 742761772
92 31 934033938
172 97 238586287
77 191 267962930
199 10 970201899
2 150 211701369
35 162 119938268
195 197 567498864
62 159 198698620
17 110 472437657
202 179 121800271
115 135 70371572
111 62 443...

output:

49909325408

result:

ok 1 number(s): "49909325408"

Test #14:

score: 0
Accepted
time: 3ms
memory: 15864kb

input:

314
26 307 692391292
279 111 226570582
290 76 261494858
132 47 708283863
253 177 82612833
32 26 881275895
248 213 349235000
240 136 227630771
133 208 894493845
295 174 760101024
191 182 333036912
309 205 326571720
138 220 582371900
185 262 33941275
113 151 91998856
194 51 532523590
219 174 90194801
...

output:

73980124774

result:

ok 1 number(s): "73980124774"

Test #15:

score: 0
Accepted
time: 4ms
memory: 16140kb

input:

472
215 64 888756595
191 437 782953525
284 151 807803141
142 382 737321722
200 373 933468526
387 190 414005694
137 464 157330847
240 55 838395267
262 74 996210474
428 42 179226852
364 446 789614149
177 66 882599216
6 278 229756157
22 325 676675321
231 131 811796299
335 86 632795653
184 433 454696152...

output:

115815454982

result:

ok 1 number(s): "115815454982"

Test #16:

score: 0
Accepted
time: 13ms
memory: 16076kb

input:

709
507 296 959229221
564 579 785837067
165 238 854583076
195 550 409079670
134 411 35472127
581 210 191747703
170 161 804804474
111 106 442762676
488 333 310679628
69 505 273768286
120 85 205745581
652 565 468876379
30 165 512567322
236 654 568944218
572 116 598480208
448 537 315385253
590 374 4940...

output:

176997131937

result:

ok 1 number(s): "176997131937"

Test #17:

score: 0
Accepted
time: 16ms
memory: 18312kb

input:

1064
1011 964 184314429
821 627 456155208
732 497 56527680
179 168 52071168
836 1005 604045343
19 401 439301716
818 500 303713286
970 268 24075641
888 744 839729821
101 97 726134962
942 260 735986500
143 436 241015562
668 910 391605524
634 635 160559352
205 50 612020502
20 360 696670729
175 575 2551...

output:

266930542461

result:

ok 1 number(s): "266930542461"

Test #18:

score: 0
Accepted
time: 24ms
memory: 16384kb

input:

1597
639 1393 166904194
1326 984 426206306
443 1524 935852282
848 1091 771776465
760 898 864783022
1379 372 38647886
481 603 346594658
521 122 293597610
1441 1589 133798182
1185 1272 279881925
544 666 231802145
1081 429 975793623
802 720 31278767
918 535 992962940
528 706 915212950
520 505 309874112...

output:

405559254752

result:

ok 1 number(s): "405559254752"

Test #19:

score: 0
Accepted
time: 48ms
memory: 16344kb

input:

2396
1981 1533 298355427
97 1737 959008541
787 1377 213392751
471 1 315600441
1995 1605 255228530
1813 309 900206470
463 536 734537574
730 2056 946098919
42 535 656307145
213 2365 598200890
582 105 100509217
1413 1740 655194157
1152 17 689800494
2106 1978 135105427
1252 999 617607068
1044 612 802184...

output:

597231143545

result:

ok 1 number(s): "597231143545"

Test #20:

score: 0
Accepted
time: 71ms
memory: 16624kb

input:

3595
1226 458 449847735
3424 1750 313050010
3169 2627 640096567
162 1184 906369956
1422 1015 293642622
340 2940 990712500
1026 1217 841244511
388 3004 899853656
896 669 146375886
2674 2297 111706208
3201 1696 323055839
351 1670 182429627
1633 511 12020195
2001 3285 41275714
248 1703 219345489
1759 1...

output:

899911898812

result:

ok 1 number(s): "899911898812"

Test #21:

score: 0
Accepted
time: 111ms
memory: 18696kb

input:

5393
2093 1287 583196596
2605 4403 533046343
3917 285 235297421
4318 4681 411844255
1588 1842 648962599
2164 2375 680797189
217 3854 531509369
4606 3646 354560797
4059 1754 976303595
1979 2652 265487574
4518 3955 157233712
2220 3416 107520029
1693 4855 722727994
4784 4162 245866252
498 1215 20109583...

output:

1349936604836

result:

ok 1 number(s): "1349936604836"

Test #22:

score: 0
Accepted
time: 194ms
memory: 16940kb

input:

8090
4866 7478 356775584
2504 3192 239406790
7743 2941 65392868
5615 1820 337863138
7340 4815 69744983
6191 1229 587983387
7729 3212 685050434
4313 5380 999113456
6515 5715 447059187
2429 7934 458547204
3870 7822 238996790
2286 3953 479733208
2620 3563 480862876
1111 6631 522438482
7956 2469 1939648...

output:

2064278617120

result:

ok 1 number(s): "2064278617120"

Test #23:

score: 0
Accepted
time: 328ms
memory: 17728kb

input:

12136
9194 7715 385468038
10307 6421 156181299
2779 9831 370946156
5449 7750 978449190
1276 844 367495644
1009 11917 41206130
4623 821 884083711
7802 3252 270221800
11699 9720 67880248
905 7498 882641163
846 10014 591139488
6648 1671 688996597
4295 12118 207178901
4320 10134 122002645
3686 10730 854...

output:

3119930013408

result:

ok 1 number(s): "3119930013408"

Test #24:

score: 0
Accepted
time: 498ms
memory: 20336kb

input:

18205
15502 9773 287504909
99 3826 342956061
5281 2167 882347909
11920 6288 432122804
12016 16973 61123860
5295 1207 911757865
14111 7883 777996097
1347 9620 363217200
660 15969 710395355
13065 15291 668428361
11892 17197 764778250
5172 9857 283025751
10253 11454 797309399
854 16916 387603881
4046 9...

output:

4646485106348

result:

ok 1 number(s): "4646485106348"

Test #25:

score: 0
Accepted
time: 795ms
memory: 21508kb

input:

27308
24579 3661 862768022
5266 18066 445716653
23679 2988 969489642
19312 17314 795242288
4196 16999 888385325
4082 25785 490546658
20278 6999 217961913
23575 3413 63174645
23253 26512 938455547
11715 7880 24996012
12751 25040 156918854
10141 15211 698329456
21632 8801 287594181
8346 4485 864856860...

output:

6953369240363

result:

ok 1 number(s): "6953369240363"

Test #26:

score: 0
Accepted
time: 1343ms
memory: 21728kb

input:

40963
32397 21728 665533394
14092 25532 885841420
6996 13499 541070446
10132 14170 968034413
34862 23452 27553808
4384 18087 951007362
40193 36533 876771802
21939 255 835996912
14813 34602 396870817
23518 12878 121167193
24674 35802 634701100
30982 21854 872559058
37114 1857 748537081
14651 28035 78...

output:

10475585732428

result:

ok 1 number(s): "10475585732428"

Test #27:

score: 0
Accepted
time: 1982ms
memory: 26100kb

input:

61445
36697 25963 94951597
7513 24837 819005409
854 59947 670876395
53706 28155 500385795
21808 12434 384290319
22180 9978 226530813
24817 39062 431206958
29985 44370 903111841
33782 7850 744209998
40702 37285 53291120
25414 271 438279520
4742 2959 465420139
4122 48945 880775407
42032 3922 82058901
...

output:

15678557202606

result:

ok 1 number(s): "15678557202606"

Test #28:

score: 0
Accepted
time: 3351ms
memory: 32308kb

input:

92168
56230 42965 742064775
4877 45898 159393199
59960 15737 139858988
83885 3886 29974986
7528 23740 133054240
42731 67896 795632101
65960 85613 760855118
22584 18115 872879663
74322 5174 466635717
16877 65430 512235721
42196 12741 698697046
13205 45782 999285629
9991 85074 537703269
11324 57987 99...

output:

23527389016280

result:

ok 1 number(s): "23527389016280"

Test #29:

score: 0
Accepted
time: 5298ms
memory: 41024kb

input:

138253
137028 98027 420176109
80718 126363 925205029
6738 78045 403027262
61401 88129 15744684
23837 119097 640220864
15996 46921 935267867
55975 15608 132891604
113324 22647 47973513
6441 33699 644316078
25548 66322 765816467
122863 55030 252850483
98023 67850 575671984
60006 91757 240693176
74046 ...

output:

35424061451157

result:

ok 1 number(s): "35424061451157"

Test #30:

score: 0
Accepted
time: 5032ms
memory: 41396kb

input:

131071
90672 123987 228449234
3604 102308 987422594
59810 25149 860613161
104850 269 689330493
24993 101682 976691697
78019 43297 520816902
71433 76386 821164796
5909 77441 120378040
45000 43490 35922905
17468 78999 878299743
1241 113223 90941807
110893 103555 180500551
91339 77238 493814644
13139 5...

output:

33473411344075

result:

ok 1 number(s): "33473411344075"

Test #31:

score: 0
Accepted
time: 4917ms
memory: 37540kb

input:

131072
61466 60099 43713848
4432 107280 858182963
105411 3399 116715084
97176 123606 720509750
25188 78189 197911350
63294 23532 650834189
29931 114646 773415808
83011 103448 15006743
36024 52158 574964066
104377 4278 481207906
98234 14071 880195643
95198 110017 473546968
90133 59609 136208461
322 5...

output:

33464721182174

result:

ok 1 number(s): "33464721182174"

Test #32:

score: 0
Accepted
time: 5268ms
memory: 42896kb

input:

131073
45917 103829 958666723
94319 91112 870672821
76150 4477 607817071
116729 95377 688420221
63089 57400 798542306
96986 104154 423949112
122218 10852 946616129
82316 122347 621862025
76160 94630 657810973
128606 83099 974721993
36605 86452 897502490
47480 70841 125116337
126918 109172 170092230
...

output:

33570691146219

result:

ok 1 number(s): "33570691146219"

Test #33:

score: -100
Time Limit Exceeded

input:

199995
15467 44256 880189728
11879 82576 277886095
88467 171050 502781139
34306 134775 937105286
128255 122988 6045953
191726 128000 120294449
184032 174614 229445343
39848 120710 778565003
164709 140201 284867637
170121 23229 628225839
83381 194905 423440701
105958 129062 548268870
157416 169550 53...

output:

51069618351288

result: