Submission #677587

#	Time	Username	Problem	Language	Result	Execution time	Memory
677587		elkernos	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	405 ms	16560 KiB

kyoto

// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
    sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
    {
sim > struct rge {
    c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
    ~debug()
    {
        cerr << endl;
    }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
    ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c &)
    {
        ris;
    }
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
#ifdef XOX
#warning Times may differ!!!
#endif
 
#define endl '\n'
#define pb emplace_back
#define vt vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
const int nax = 1000 * 1007, mod = 1e9 + 7;
 
struct wek {
    int p, q, i;
    bool operator<(const wek &he) const
    {
        if ((ll)p * he.q != (ll)q * he.p) return (ll)p * he.q < (ll)q * he.p;
        if (q != he.q) return q < he.q;
        return i < he.i;
    }
};
 
int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int h, w;
    cin >> h >> w;
    vt<int> a(h), b(w);
    for (auto &i : a) cin >> i;
    for (auto &i : b) cin >> i;
    vt<int> na(h), nb(w);
    for (int i = 0; i < h; i++) na[i] = i + 1;
    for (int i = 0; i < w; i++) nb[i] = i + 1;
    set<wek> poz, pio;
    for (int i = 0; i < h - 1; i++) poz.insert({a[i + 1] - a[i], 1, i});
    for (int i = 0; i < w - 1; i++) pio.insert({b[i + 1] - b[i], 1, i});
    poz.insert({(int)-2e9, 1, 1});
    pio.insert({(int)-2e9, 1, 1});
    ll ans = 0;
    while (sz(pio) > 1 || sz(poz) > 1) {
        if (*pio.rbegin() < *poz.rbegin()) {
            auto [p, q, i] = *poz.rbegin();
            poz.erase({p, q, i});
            int j = na[i];
            if (j == (int)a.size() - 1) {
                while (q--) {
                    ans += b.back(); a.pop_back();
                }
            }
            else {
                int k = na[j];
                poz.erase({a[k] - a[j], k - j, j}); poz.insert({a[k] - a[i], k - i, i});
                na[i] = k;
            }
        }
        else {
            auto [p, q, i] = *pio.rbegin();
            pio.erase({p, q, i});
            int j = nb[i];
            if (j == (int)b.size() - 1) {
                while (q--) {
                    ans += a.back(); b.pop_back();
                }
            }
            else {
                int k = nb[j];
                pio.erase({b[k] - b[j], k - j, j}); pio.insert({b[k] - b[i], k - i, i});
                nb[i] = k;
            }
        }
    }
    cout << ans << endl;
}

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