Submission #545147

#	Time	Username	Problem	Language	Result	Execution time	Memory
545147		leaked	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	420 ms	16572 KiB

kyoto

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int M=1e9+7;
struct buben{
    int dt;
    int dl;
    int i;
    int tp;
    buben(int _a,int _b,int _c,int _t) : dt(_a),dl(_b),i(_c),tp(_t){}
    const bool operator <(const buben &o) const{
        return make_tuple(1ll*dt*o.dl,dl,i,tp)<make_tuple(1ll*dl*o.dt,o.dl,o.i,o.tp);
    }
};
set<buben> st;
signed main(){
    fast_resp;
    int n,m;
    cin>>n>>m;
    vec<int>a(n);
    vec<int>b(m);
    for(auto &z : a) cin>>z;
    for(auto &z : b) cin>>z;
    vec<int> la(n),lb(m);
    for(int i=0;i+1<n;i++) la[i]=i+1,st.insert(buben(a[i+1]-a[i],1,i,0));
    for(int i=0;i+1<m;i++) lb[i]=i+1,st.insert(buben(b[i+1]-b[i],1,i,1));
    ll ans=0;
    while(sz(st)){
        int i=st.rbegin()->i;
        int dl=st.rbegin()->dl;
        int typ=st.rbegin()->tp;
        st.erase(--st.end());
//        cout<<"W "<<dl<<' '<<i<<endl;
        if(typ==0){
            if(la[i]==sz(a)-1){
                while(dl--){
                    ans+=b.back();
                    a.pop_back();
                }
            }
            else{
                int j=la[i];
                st.erase(buben(a[la[j]]-a[j],la[j]-j,j,0));
                la[i]=la[j];
                st.insert(buben(a[la[i]]-a[i],la[i]-i,i,0));
            }
        }
        else{
            if(lb[i]==sz(b)-1){
                while(dl--){
                    ans+=a.back();
                    b.pop_back();
                }
            }
            else{
                int j=lb[i];
                st.erase(buben(b[lb[j]]-b[j],lb[j]-j,j,1));
                lb[i]=lb[j];
//                cout<<"WT "<<i<<' '<<lb[i]<<' '<<lb[i]-i<<endl;
                st.insert(buben(b[lb[i]]-b[i],lb[i]-i,i,1));
            }
        }
    }
    cout<<ans;
    return 0;
}
/*

*/

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