QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#456246 | #3304. Interval Graph | Kevin5307 | WA | 27ms | 49380kb | C++23 | 2.1kb | 2024-06-27 16:11:28 | 2024-06-27 16:11:28 |
Judging History
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'