Submission #1207872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207872		emptypringlescan	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	637 ms	27052 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
int n,m;
long long arr[2][100005];
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> arr[0][i];
    for(int i=1; i<=m; i++) cin >> arr[1][i];
    set<int> alive[2];
    set<pair<long double,pair<int,int> > > all;
    for(int i=1; i<=n; i++){
		alive[0].insert(i);
		if(i>1) all.insert({(long double)(arr[0][i-1]-arr[0][i])/1,{0,i}});
	}
	for(int i=1; i<=m; i++){
		alive[1].insert(i);
		if(i>1) all.insert({(long double)(arr[1][i-1]-arr[1][i])/1,{1,i}});
	}
	long long ans=0;
	int l0=n,l1=m;
	while(l0!=1&&l1!=1){
		auto x=*all.begin();
		all.erase(all.begin());
		//cout << x.second.first << ' ' << x.second.second << '\n';
		if(x.second.first==0){
			alive[0].erase(x.second.second);
			if(x.second.second>*(--alive[0].end())){
				ans+=(long long)(x.second.second-*(--alive[0].end()))*arr[1][*(--alive[1].end())];
			}
			else{
				int y=*alive[0].lower_bound(x.second.second);
				int p=*(--alive[0].lower_bound(x.second.second));
				all.erase({(long double)(arr[0][x.second.second]-arr[0][y])/(y-x.second.second),{0,y}});
				all.insert({(long double)(arr[0][p]-arr[0][y])/(y-p),{0,y}});
			}
			l0--;
		}
		else{
			alive[1].erase(x.second.second);
			if(x.second.second>*(--alive[1].end())){
				ans+=(long long)(x.second.second-*(--alive[1].end()))*arr[0][*(--alive[0].end())];
			}
			else{
				int y=*alive[1].lower_bound(x.second.second);
				int p=*(--alive[1].lower_bound(x.second.second));
				all.erase({(long double)(arr[1][x.second.second]-arr[1][y])/(y-x.second.second),{1,y}});
				all.insert({(long double)(arr[1][p]-arr[1][y])/(y-p),{1,y}});
			}
			l1--;
		}
		//cout << ans << '\n';
	}
	if(l0==1){
		ans+=(*(--alive[1].end())-1)*arr[0][*(--alive[0].end())];
	}
	else{
		ans+=(*(--alive[0].end())-1)*arr[1][*(--alive[1].end())];
	}
	cout << ans;
} 

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