Submission #915041

#	Time	Username	Problem	Language	Result	Execution time	Memory
915041		minhnhatnoe	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	374 ms	16512 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct choice{
    int a, posl, posr;
    choice(int a, int posl, int posr): a(a), posl(posl), posr(posr) {}
    friend bool operator<(const choice &lhs, const choice &rhs){
        ll l = 1LL * lhs.a * (rhs.posr - rhs.posl), r = 1LL * rhs.a * (lhs.posr - lhs.posl);
        if (l != r) return l < r;
        return lhs.posl < rhs.posl;
    }
};

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    
    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i=0; i<n; i++) cin >> a[i];
    for (int j=0; j<m; j++) cin >> b[j];

    const int MAXV = 1000000000;
    set<choice> s;
    vector<int> nxta(n), nxtb(m);
    for (int i=1; i<n; i++){
        nxta[i-1] = i;
        s.emplace(a[i-1] - a[i], i-1, i);
    }
    nxta.back() = -1;
    for (int i=1; i<m; i++){
        nxtb[i-1] = i;
        s.emplace(b[i-1] - b[i], i-1 + MAXV, i + MAXV);
    }
    nxtb.back() = -1;
    
    ll result = 0;
    int lasta = n-1, lastb = m-1;
    while (s.size()){
        choice c = *s.begin(); s.erase(s.begin());
        if (c.posl < MAXV){
            int nxtpos = nxta[c.posl] = nxta[c.posr];
            nxta[c.posr] = -1;

            if (nxtpos == -1){
                result += 1LL * b[lastb] * (c.posr - c.posl);
                // cout << "B: " << lastb << " " << b[lastb] << "\n";
                // cout << s.size() << "\n";
                lasta = c.posl;
            }
            else{
                // cout << "SUS: " << s.size();
                s.erase(s.find(choice(a[c.posr] - a[nxtpos], c.posr, nxtpos)));
                s.emplace(a[c.posl] - a[nxtpos], c.posl, nxtpos);
                // cout << " " << s.size() << "\n";
            }
        }
        else{
            c.posl -= MAXV, c.posr -= MAXV;

            int nxtpos = nxtb[c.posl] = nxtb[c.posr];
            nxtb[c.posr] = -1;

            if (nxtpos == -1){
                result += 1LL * a[lasta] * (c.posr - c.posl);
                // cout << "A: " << lasta << " " << a[lasta] << "\n";
                // cout << s.size() << "\n";
                lastb = c.posl;
            }
            else{
                // cout << "SUS: " << s.size();
                s.erase(s.find(choice(b[c.posr] - b[nxtpos], c.posr + MAXV, nxtpos + MAXV)));
                s.emplace(b[c.posl] - b[nxtpos], c.posl + MAXV, nxtpos + MAXV);
                // cout << " " << s.size() << "\n";
            }
        }
    }
    cout << result << "\n";
}

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