QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456246#3304. Interval GraphKevin5307WA 27ms49380kbC++232.1kb2024-06-27 16:11:282024-06-27 16:11:28

Judging History

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

  • [2024-06-27 16:11:28]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:49380kb
  • [2024-06-27 16:11:28]
  • 提交

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) greverse(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
void die(string S){puts(S.c_str());exit(0);}
int n;
int l[300300],r[300300];
ll w[300300];
ll dp[500500];
int lst[500500];
int choose[500500];
ll dist[500500];
int inque[500500];
vector<pair<int,ll>> G[500500];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>l[i]>>r[i]>>w[i];
	vector<pii> vec;
	for(int i=1;i<=n;i++)
		vec.pb(l[i],i);
	srt(vec);
	int p=0;
	memset(dp,-inf,sizeof(dp));
	dp[0]=0;
	for(int i=0;i<=500000;i++)
	{
		if(dp[i]>dp[i+1])
		{
			dp[i+1]=dp[i];
			lst[i+1]=-1;
		}
		while(p<sz(vec)&&vec[p].first==i+1)
		{
			if(dp[i]+w[vec[p].second]>dp[r[vec[p].second]])
			{
				dp[r[vec[p].second]]=dp[i]+w[vec[p].second];
				lst[r[vec[p].second]]=vec[p].second;
			}
			p++;
		}
	}
	ll ans=dp[500000];
	int cur=500000;
	while(cur)
	{
		if(lst[cur]==-1) cur--;
		else
		{
			choose[lst[cur]]=1;
			cur=l[lst[cur]]-1;
		}
	}
	memset(dist,-inf,sizeof(dist));
	queue<int> q;
	q.push(0);
	inque[0]=1;
	dist[0]=0;
	for(int i=1;i<=500000;i++)
		G[i-1].pb(i,0);
	for(int i=1;i<=n;i++)
		if(!choose[i])
			G[l[i]-1].pb(r[i],w[i]);
		else
			G[r[i]].pb(l[i]-1,-w[i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inque[x]=0;
		for(auto pr:G[x])
			if(pr.second+dist[x]>dist[pr.first])
			{
				dist[pr.first]=pr.second+dist[x];
				if(!inque[pr.first])
				{
					q.push(pr.first);
					inque[pr.first]=1;
				}
			}
	}
	cout<<ans+dist[500000]<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 14ms
memory: 47776kb

input:

3
1 3 10
3 5 20
5 7 30

output:

60

result:

ok single line: '60'

Test #2:

score: 0
Accepted
time: 12ms
memory: 48360kb

input:

3
1 3 1
2 3 2
3 3 3

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 20ms
memory: 46828kb

input:

5
273688 490724 141869495469
154210 248799 742530996682
149091 491274 531295833012
174801 345648 278781521855
102024 399466 621084696102

output:

1505485188253

result:

ok single line: '1505485188253'

Test #4:

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

input:

5
105810 416405 592884319111
68883 461849 250489784736
128007 390711 236479393395
110994 160261 671859872475
39895 354649 821557846804

output:

1493417719279

result:

ok single line: '1493417719279'

Test #5:

score: 0
Accepted
time: 19ms
memory: 48860kb

input:

5
74034 352895 387389006450
128646 447773 985594949211
116692 479464 753465491369
88207 164196 460965261831
310907 348457 244166716943

output:

1739060440580

result:

ok single line: '1739060440580'

Test #6:

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

input:

5
136223 315153 624871957613
123513 430694 514457730848
144122 163401 180633227331
70425 457509 583010340443
120858 358890 332106336020

output:

1207882298056

result:

ok single line: '1207882298056'

Test #7:

score: 0
Accepted
time: 19ms
memory: 47944kb

input:

5
32831 184060 188789421601
171427 329018 209530344935
161895 313664 844808531262
75336 382835 990150112615
368344 494450 383137311031

output:

2218095954908

result:

ok single line: '2218095954908'

Test #8:

score: 0
Accepted
time: 20ms
memory: 48500kb

input:

5
33097 167528 56416700595
78929 101983 55562283422
50281 247721 72636194105
57340 339774 753069033730
197700 361406 203188153213

output:

1012673887538

result:

ok single line: '1012673887538'

Test #9:

score: 0
Accepted
time: 26ms
memory: 47592kb

input:

5
136258 419364 970361584457
174267 423756 981896731618
218696 320621 799128240377
277844 388844 345834192912
326149 436675 517068146274

output:

2298093118269

result:

ok single line: '2298093118269'

Test #10:

score: 0
Accepted
time: 12ms
memory: 47792kb

input:

5
333403 365451 537561752876
244632 361560 741776349264
2218 229609 10595278802
337055 425647 647565847251
318064 408347 468418159265

output:

1399937475317

result:

ok single line: '1399937475317'

Test #11:

score: 0
Accepted
time: 22ms
memory: 48844kb

input:

5
305912 356193 234556428936
34253 146174 554916208323
354663 382256 501013406841
45319 313082 761965038322
89846 114859 406147662810

output:

2052451082422

result:

ok single line: '2052451082422'

Test #12:

score: 0
Accepted
time: 17ms
memory: 47968kb

input:

5
10484 386673 674957728098
123005 450911 341635545468
199576 219764 182440191590
8228 169007 33905834946
145538 211849 446485748684

output:

1121443476782

result:

ok single line: '1121443476782'

Test #13:

score: 0
Accepted
time: 23ms
memory: 47912kb

input:

5
196155 216384 215933148505
318876 435000 353829017744
122721 398621 58734912743
533 238849 856486333719
66200 250933 4453945996

output:

1426248499968

result:

ok single line: '1426248499968'

Test #14:

score: 0
Accepted
time: 15ms
memory: 49296kb

input:

5
91236 168330 90354269558
218682 390889 191205075883
221683 493083 497918647229
117474 419937 358256123269
416422 453062 554087430692

output:

1333565423362

result:

ok single line: '1333565423362'

Test #15:

score: 0
Accepted
time: 27ms
memory: 49380kb

input:

5
237922 414694 492791392236
200810 295732 703837767479
80849 423897 910310765595
225197 246617 253402130446
179804 218858 140534479355

output:

1614148533074

result:

ok single line: '1614148533074'

Test #16:

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

input:

5
41929 300931 944331027727
172666 330417 160847432302
96286 113241 63372527926
40867 216156 223392679613
2594 364462 733811708804

output:

1678142736531

result:

ok single line: '1678142736531'

Test #17:

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

input:

5
149362 275221 743901732699
56820 63687 656767349940
48803 416252 30388045831
10253 490848 438410675855
95963 258763 737529907846

output:

2138198990485

result:

ok single line: '2138198990485'

Test #18:

score: 0
Accepted
time: 8ms
memory: 48232kb

input:

5
263018 373835 428350273686
29375 111905 375640479584
25231 174870 832328659881
256277 346665 898287217911
238721 460504 367473312117

output:

2534606631062

result:

ok single line: '2534606631062'

Test #19:

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

input:

5
403708 447891 992157496819
111375 353523 122135869693
229322 423973 20556361975
261462 369014 103826845743
273450 472665 919831236649

output:

2034124603161

result:

ok single line: '2034124603161'

Test #20:

score: -100
Wrong Answer
time: 12ms
memory: 48700kb

input:

5
377042 471720 754973059247
125073 417498 462936493167
36335 122931 885958721333
9163 208425 64065945078
248923 445028 340586669747

output:

2103868273747

result:

wrong answer 1st lines differ - expected: '2167934218825', found: '2103868273747'