Submission #1141314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141314		byunjaewoo	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	260 ms	18708 KiB

kyoto

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010;
int n, m, ans, a[N], b[N], l1[N], l2[N];
set<int> s1, s2;
struct Data {
    int d, n, i;
    bool operator<(const Data&r) const {return d*r.n<r.d*n;}
};
priority_queue<Data> pq;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i], s1.insert(i);
    for(int i=1; i<=m; i++) cin>>b[i], s2.insert(i);
    for(int i=1; i<n; i++) pq.push({a[i+1]-a[i], 1, i}), l1[i+1]=i;
    for(int i=1; i<m; i++) pq.push({b[i+1]-b[i], 1, -i}), l2[i+1]=i;
    for(int i=1; i<=n+m-2; i++) {
        Data tmp=pq.top(); pq.pop();
        if(tmp.i>0) {
            if(s1.upper_bound(tmp.i)==s1.end()) {
                i--; continue;
            }
            if(l1[*s1.upper_bound(tmp.i)]!=tmp.i) {
                i--; continue;
            }
            s1.erase(s1.upper_bound(tmp.i));
            if(s1.upper_bound(tmp.i)==s1.end()) ans+=b[*s2.rbegin()]*tmp.n;
            else {
                int p=(*s1.upper_bound(tmp.i));
                pq.push({a[p]-a[tmp.i], p-tmp.i, tmp.i}), l1[p]=tmp.i;
            }
        }
        else {
            tmp.i*=-1;
            if(s2.upper_bound(tmp.i)==s2.end()) {
                i--; continue;
            }
            if(l2[*s2.upper_bound(tmp.i)]!=tmp.i) {
                i--; continue;
            }
            s2.erase(s2.upper_bound(tmp.i));
            if(s2.upper_bound(tmp.i)==s2.end()) ans+=a[*s1.rbegin()]*tmp.n;
            else {
                int p=(*s2.upper_bound(tmp.i));
                pq.push({b[p]-b[tmp.i], p-tmp.i, -tmp.i}), l2[p]=tmp.i;
            }
        }
    }
    cout<<ans;
    return 0;
}

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