Submission #1127584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127584		Warinchai	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	125 ms	17072 KiB

kyoto

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x[100005];
int y[100005];
int p[200005];
int fp(int a){return p[a]==a?a:p[a]=fp(p[a]);}
int un(int a,int b){return p[fp(b)]=fp(a);}
int ver[200005];
int ans=0;
struct node{
    int sum,freq;
    node(int _sum=0,int _freq=0){
        sum=_sum,freq=_freq;
    }
    friend bool operator<(node a,node b){
        return (a.sum*b.freq)>(b.sum*a.freq);
    }
    friend node operator+(node a,node b){
        ans+=a.sum*b.freq;
        //cerr<<"add:"<<a.sum<<"*"<<b.freq<<"\n";
        return node(a.sum+b.sum,a.freq+b.freq);
    }
};
node info[200005];
int pa[200005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int h,w;cin>>h>>w;
    for(int i=1;i<=h;i++)cin>>x[i];
    for(int i=1;i<=w;i++)cin>>y[i];
    ans+=x[1]*(w-1)+y[1]*(h-1);
    priority_queue<pair<node,pair<int,int>>>pq;
    for(int i=1;i<=h+w;i++)p[i]=i;
    for(int i=2;i<=h;i++){
        info[i]=node(x[i]-x[i-1],1);
        pa[i]=i-1;
        pq.push({info[i],{i,++ver[i]}});
        ans-=(x[i]-x[i-1])*(h-i);
    }
    for(int i=1;i<w;i++){
        info[h+i]=node(y[i+1]-y[i],1);
        pa[h+i]=(i==1?1:h+i-1);
        pq.push({info[h+i],{h+i,++ver[h+i]}});
        ans-=(y[i+1]-y[i])*(w-i-1);
    }
    //cerr<<ans<<"\n";
    //cerr<<"work\n";
    while(!pq.empty()){
        int x=pq.top().second.first;
        int tv=pq.top().second.second;
        pq.pop();
        if(x==1)continue;
        if(ver[x]!=tv)continue;
        //cerr<<x<<" "<<fp(pa[x])<<"\n";
        info[fp(pa[x])]=info[fp(pa[x])]+info[fp(x)];
        un(pa[x],x);
        ver[fp(pa[x])]++;
        pq.push({info[fp(pa[x])],{fp(pa[x]),ver[fp(pa[x])]}});
    }
    cout<<ans;
}

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