Submission #1126119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126119		_8_8_	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	23 ms	2244 KiB

kyoto

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

const int  N = (int)1e5 + 12, MOD = 998244353;

struct vec{
    ll x, y;
};
bool check(vec a, vec b) {
    return (a.x * b.y - b.x * a.y >= 0);
}
vector<int> get(int n, int a[]) {
    vector<int> st;
    for(int i = n; i >= 1; i--) {
        while((int)st.size() >= 2) {
            int j = st.back(), k = st[(int)st.size() - 2];
            if((a[j] - a[i]) * 1ll * (k - j) - (a[k] - a[j]) * 1ll * (j - i)  > 0) {
                st.pop_back();
            } else break;
        }
        st.push_back(i);
    }
    reverse(st.begin(), st.end());
    return st;
}
int n, m, a[N], b[N];

void test() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    vector<int> x = get(n, a), y = get(m, b);
    n = (int)x.size(), m = (int)y.size();
    int px = 0, py = 0;
    ll res = 0;
    while(px < n - 1 || py < m - 1) {
        if(px == n - 1) {
            res += (y[py + 1] - y[py]) * 1ll * a[x[px]];
            py++;
        } else if(py == m - 1) {
            res += (x[px + 1] - x[px]) * 1ll * b[y[py]];
            px++;
        } else {
            vec A = {a[x[px + 1]] - a[x[px]], x[px + 1] - x[px]};
            vec B = {b[y[py + 1]] - b[y[py]], y[py + 1] - y[py]};
            if(!check(A, B)) {
                res += (x[px + 1] - x[px]) * 1ll * b[y[py]];
                px++;
            } else {
                res += (y[py + 1] - y[py]) * 1ll * a[x[px]];
                py++;
            }
        }
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}   

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