QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352338 | #7993. 哈密顿 | Kevin5307 | ML | 290ms | 13220kb | C++20 | 1.9kb | 2024-03-13 09:57:22 | 2024-03-13 09:57:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
mt19937_64 rnd(20210448);
ull prior[200200];
int ls[200200],rs[200200],siz[200200],tot;
ll sum[200200],val[200200];
void pushup(int x)
{
siz[x]=siz[ls[x]]+siz[rs[x]]+1;
sum[x]=sum[ls[x]]+sum[rs[x]]+val[x];
}
int merge(int a,int b)
{
if(!a||!b) return a+b;
if(prior[a]>prior[b])
{
rs[a]=merge(rs[a],b);
pushup(a);
return a;
}
else
{
ls[b]=merge(a,ls[b]);
pushup(b);
return b;
}
}
void sSplit(int x,int s,int &a,int &b)
{
if(!x)
{
a=b=0;
return ;
}
if(siz[ls[x]]>=s)
{
b=x;
sSplit(ls[x],s,a,ls[b]);
pushup(b);
}
else
{
a=x;
sSplit(rs[x],s-siz[ls[x]]-1,rs[a],b);
pushup(a);
}
}
void vSplit(int x,ll v,int &a,int &b)
{
if(!x)
{
a=b=0;
return ;
}
if(val[x]<=v)
{
a=x;
vSplit(rs[x],v,rs[a],b);
pushup(a);
}
else
{
b=x;
vSplit(ls[x],v,a,ls[b]);
pushup(b);
}
}
ll aa[100100],bb[100100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>aa[i]>>bb[i];
vector<ll> vec;
for(int i=1;i<=n;i++)
vec.push_back(aa[i]);
for(int i=1;i<=n;i++)
vec.push_back(bb[i]);
sort(vec.begin(),vec.end());
int rt=0;
for(auto x:vec)
{
tot++;
prior[tot]=rnd();
siz[tot]=1;
val[tot]=sum[tot]=x;
rt=merge(rt,tot);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
int a,b,c,d;
vSplit(rt,aa[i]-1,a,b);
sSplit(b,1,b,c);
a=merge(a,c);
vSplit(rt,bb[i]-1,a,c);
sSplit(c,1,c,d);
a=merge(a,d);
sSplit(a,n,a,d);
ans=max(ans,sum[d]+aa[i]+bb[i]);
a=merge(a,d);
vSplit(a,aa[i],a,d);
a=merge(a,merge(b,d));
vSplit(a,bb[i],a,d);
a=merge(a,merge(c,d));
}
ll sa=0,sb=0;
for(int i=1;i<=n;i++)
{
sa+=aa[i];
sb+=bb[i];
}
ans=max({ans,sa,sb});
ll sum=0;
for(auto x:vec)
sum+=x;
cout<<ans+ans-sum<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7728kb
input:
3 1 10 8 2 4 5
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
2 732734236 669531729 368612323 916696032
output:
484881202
result:
ok single line: '484881202'
Test #3:
score: 0
Accepted
time: 290ms
memory: 13220kb
input:
96739 960257511 790393830 766983782 374475134 476482176 529858300 310917487 76906076 81191659 653180897 119832756 362638666 228783015 626981197 74837554 781854003 663345706 153150021 576244413 708232220 842559077 417230462 249522463 815253339 391663517 742521049 60507117 258429449 112143256 81408991...
output:
48459768018811
result:
ok single line: '48459768018811'
Test #4:
score: -100
Memory Limit Exceeded
input:
96785 270111821 467151412 338110212 587493839 880232679 190826309 757074784 388758646 266705411 248083736 932249293 549449409 813345622 128324633 997551674 739367275 118482916 584132988 530659142 718566145 843527299 299368287 351399254 123105310 94363217 996225281 372809651 824469842 227112349 94127...