Submission #567446

#TimeUsernameProblemLanguageResultExecution timeMemory
567446jamezzzSightseeing in Kyoto (JOI22_kyoto)C++17
100 / 100
319 ms14496 KiB
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define fi first #define se second #define LINF 1023456789123456789 typedef long long ll; typedef pair<int,int> ii; typedef pair<double,ii> iii; int h,w; ll a[100005],b[100005]; priority_queue<iii,vector<iii>,greater<iii>> pqh,pqv; set<int> s1,s2; inline ll rd(){ ll x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } int main(){ h=(int)rd(),w=(int)rd(); for(int i=1;i<=h;++i){ a[i]=rd(); s1.insert(i); if(i>1)pqh.push({a[i-1]-a[i],{i-1,i}}); } for(int i=1;i<=w;++i){ b[i]=rd(); s2.insert(i); if(i>1)pqv.push({b[i-1]-b[i],{i-1,i}}); } pqh.push({LINF,{-1,-1}}); pqv.push({LINF,{-1,-1}}); ll ans=0; while(pqh.size()+pqv.size()>2){ if(pqh.top().fi<pqv.top().fi){ ii p=pqh.top().se;pqh.pop(); if(!s1.count(p.fi)||!s1.count(p.se))continue;//already removed adjacent thing int l=p.fi,r=-1; auto it=s1.find(p.se); if(it!=--s1.end())r=*next(it); s1.erase(it); if(r!=-1){ pqh.push({(double)(a[l]-a[r])/(r-l),{l,r}}); } else ans+=b[*(--s2.end())]*(p.se-p.fi); } else{ ii p=pqv.top().se;pqv.pop(); if(!s2.count(p.fi)||!s2.count(p.se))continue;//already removed adjacent thing int l=p.fi,r=-1; auto it=s2.find(p.se); if(it!=--s2.end())r=*next(it); s2.erase(it); if(r!=-1){ pqv.push({(double)(b[l]-b[r])/(r-l),{l,r}}); } else ans+=a[*(--s1.end())]*(p.se-p.fi); } } pf("%lld\n",ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...