Submission #567446

#	Time	Username	Problem	Language	Result	Execution time	Memory
567446		jamezzz	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	319 ms	14496 KiB

kyoto

#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);
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60