Submission #787100

#	Time	Username	Problem	Language	Result	Execution time	Memory
787100		eltu0815	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	569 ms	28276 KiB

kyoto

#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define inf (1987654321)
 
using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
int n, m, q;
int mxr[100005], mxc[100005];
ll a[100005], b[100005];
double da[100005], db[100005];
set<pair<double, ll> > st;
set<int> r, c;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= m; ++i) cin >> b[i];
    
    for(int i = 2; i <= n; ++i) st.insert({a[i] - a[i - 1], i}), da[i] = a[i] - a[i - 1];
    for(int i = 2; i <= m; ++i) st.insert({b[i] - b[i - 1], i + n}), db[i] = b[i] - b[i - 1];
    for(int i = 1; i <= n; ++i) r.insert(i);
    for(int i = 1; i <= m; ++i) c.insert(i);
    
    while(!st.empty()) {
        auto mn = *st.rbegin(); st.erase(st.find(mn));
        if(mn.second <= n) {
            mxc[*c.rbegin()] = max((ll)mxc[*c.rbegin()], mn.second);
            if(*r.rbegin() != mn.second) {
                ll nxtr = *next(r.find(mn.second)), prvr = *prev(r.find(mn.second));
                st.erase({da[nxtr], nxtr});
                da[nxtr] = (double)(a[nxtr] - a[prvr])/(nxtr - prvr);
                st.insert({da[nxtr], nxtr});
            }
            r.erase(r.find(mn.second));
        }
        else {
            mn.second -= n;
            mxr[*r.rbegin()] = max((ll)mxr[*r.rbegin()], mn.second);
            if(*c.rbegin() != mn.second) {
                ll nxtc = *next(c.find(mn.second)), prvc = *prev(c.find(mn.second));
                st.erase({db[nxtc], nxtc + n});
                db[nxtc] = (double)(b[nxtc] - b[prvc])/(nxtc - prvc);
                st.insert({db[nxtc], nxtc + n});
            }
            c.erase(c.find(mn.second));
        }
    }
    
    for(int i = 2; i <= n; ++i) mxr[i] = max(mxr[i], mxr[i - 1]);
    for(int i = 2; i <= m; ++i) mxc[i] = max(mxc[i], mxc[i - 1]);
    
    ll ans = 0;
    int r = 1, c = 1, t = mxr[r] != 0 ? 1 : 0;
    while(r != n || c != m) {
        if(t) {
            ans += a[r] * abs(mxr[r] - c);
            c = mxr[r];
        }
        else {
            ans += b[c] * abs(mxc[c] - r);
            r = mxc[c];
        }
        t = !t;
    } 
    cout << ans;
    return 0;
}

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