Submission #951301

#	Time	Username	Problem	Language	Result	Execution time	Memory
951301		hotboy2703	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	490 ms	26108 KiB

kyoto

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 1e5;
ll n[2];
ll a[2][MAXN+100];
struct frac{
    ll x,y;
    bool operator < (const frac &p)const{
        return (p.y * y < 0) ^ (x*p.y<p.x*y);
    }
};
set <pair <frac,ll> > seg[2];
set <ll> s[2];
pair <frac,ll> cv(bool o,ll x1,ll x2){
    return MP(frac({a[o][x2]-a[o][x1],x2-x1}),x2);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n[0]>>n[1];
    for (ll j = 0;j < 2;j ++){
        for (ll i = 1;i <= n[j];i ++)cin>>a[j][i];
    }
    for (ll j = 0;j < 2;j ++){
        for (ll i = 1;i <= n[j];i ++){
            s[j].insert(i);
            if (i>1)seg[j].insert(MP(frac({a[j][i]-a[j][i-1],1}),i));
        }
    }
    ll ans = 0;
    while (sz(s[0]) > 1 && sz(s[1]) > 1){
        bool o = (*seg[0].rbegin()).fi < (*seg[1].rbegin()).fi;
        ll x = (*seg[o].rbegin()).se;
//        cout<<o<<' '<<x<<' '<<a[o][x]<<endl;
//        seg[o].erase(*seg[o].rbegin());
//        assert(s[o].find(x)!=s[o].end());
        if (x==*s[o].rbegin()){
            auto tmp = s[o].find(x);
            seg[o].erase(cv(o,*prev(tmp),x));
            ans += (x-*prev(tmp)) * a[!o][*s[!o].rbegin()];
        }
        else{
            if (x==*s[o].begin()){
                auto tmp = s[o].find(x);
                seg[o].erase(cv(o,x,*next(tmp)));
            }
            else{
                auto tmp = s[o].find(x);
                seg[o].erase(cv(o,*prev(tmp),x));
                seg[o].erase(cv(o,x,*next(tmp)));
                ll x1 = *prev(tmp),x2 = *next(tmp);
                seg[o].insert(cv(o,x1,x2));
            }
        }
        s[o].erase(x);
    }
    if (sz(s[0])==1)ans += (*s[1].rbegin() - 1) * a[0][1];
    else ans += (*s[0].rbegin() - 1) * a[1][1];
    cout<<ans;
}
/*
6 8
3 5 1 9 4 8
3 6 7 1 8 2 5 6
*/

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