Submission #870985

#	Time	Username	Problem	Language	Result	Execution time	Memory
870985		EJIC_B_KEDAX	Sightseeing in Kyoto (JOI22_kyoto)	C++17	40 / 100	1844 ms	16008 KiB

kyoto

#ifdef LOCAL
    //#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
 
#ifndef LOCAL
    // #pragma GCC optimize("O3")
    // #pragma GCC optimize("Ofast")
    // #pragma GCC optimize("unroll-loops")
    // #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
 namespace fastio {
    static constexpr uint32_t SZ = 1 << 17;
    char ibuf[SZ];
    char obuf[SZ];
    uint32_t pil = 0, pir = 0, por = 0;

    struct Pre {
        char num[40000];

        constexpr Pre() : num() {
            for (int i = 0; i < 10000; i++) {
                int n = i;
                for (int j = 3; j >= 0; j--) {
                    num[i * 4 + j] = n % 10 + '0';
                    n /= 10;
                }
            }
        }
    } constexpr pre;

    __attribute__((target("avx2"), optimize("O3"))) inline void load() {
        memcpy(ibuf, ibuf + pil, pir - pil);
        pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
        pil = 0;
    }

    __attribute__((target("avx2"), optimize("O3"))) inline void flush() {
        fwrite(obuf, 1, por, stdout);
        por = 0;
    }

    inline void read(char &c) { c = ibuf[pil++]; }

    template<typename T>
    __attribute__((target("avx2"), optimize("O3"))) inline void read(T &x) {
        if (pil + 32 > pir) load();
        char c;
        do
            read(c);
        while (c < '-');
        bool minus = 0;
        if (std::is_signed<T>::value) {
            if (c == '-') {
                minus = 1;
                read(c);
            }
        }
        x = 0;
        while (c >= '0') {
            x = x * 10 + (c & 15);
            read(c);
        }
        if (std::is_signed<T>::value) {
            if (minus) x = -x;
        }
    }

    inline void write(char c) { obuf[por++] = c; }

    template<typename T>
    __attribute__((target("avx2"), optimize("O3"))) inline void write(T x) {
        if (por + 32 > SZ) flush();
        if (!x) {
            write('0');
            return;
        }
        if (std::is_signed<T>::value) {
            if (x < 0) {
                write('-');
                x = -x;
            }
        }
        if (x >= 10000000000000000) {
            uint32_t r1 = x % 100000000;
            uint64_t q1 = x / 100000000;
            uint32_t r2 = q1 % 100000000;
            uint32_t q2 = q1 / 100000000;
            uint32_t n1 = r1 % 10000;
            uint32_t n2 = r1 / 10000;
            uint32_t n3 = r2 % 10000;
            uint32_t n4 = r2 / 10000;
            if (x >= 1000000000000000000) {
                uint32_t q3 = (q2 * 20972) >> 21;
                uint32_t r3 = q2 - q3 * 100;
                uint32_t q4 = (r3 * 205) >> 11;
                uint32_t r4 = r3 - q4 * 10;
                obuf[por + 0] = '0' + q3;
                obuf[por + 1] = '0' + q4;
                obuf[por + 2] = '0' + r4;
                memcpy(obuf + por + 3, pre.num + (n4 << 2), 4);
                memcpy(obuf + por + 7, pre.num + (n3 << 2), 4);
                memcpy(obuf + por + 11, pre.num + (n2 << 2), 4);
                memcpy(obuf + por + 15, pre.num + (n1 << 2), 4);
                por += 19;
            } else if (x >= 100000000000000000) {
                uint32_t q3 = (q2 * 205) >> 11;
                uint32_t r3 = q2 - q3 * 10;
                obuf[por + 0] = '0' + q3;
                obuf[por + 1] = '0' + r3;
                memcpy(obuf + por + 2, pre.num + (n4 << 2), 4);
                memcpy(obuf + por + 6, pre.num + (n3 << 2), 4);
                memcpy(obuf + por + 10, pre.num + (n2 << 2), 4);
                memcpy(obuf + por + 14, pre.num + (n1 << 2), 4);
                por += 18;
            } else {
                obuf[por + 0] = '0' + q2;
                memcpy(obuf + por + 1, pre.num + (n4 << 2), 4);
                memcpy(obuf + por + 5, pre.num + (n3 << 2), 4);
                memcpy(obuf + por + 9, pre.num + (n2 << 2), 4);
                memcpy(obuf + por + 13, pre.num + (n1 << 2), 4);
                por += 17;
            }
        } else {
            int i = 8;
            char buf[12];
            while (x >= 10000) {
                memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
                x /= 10000;
                i -= 4;
            }
            if (x < 100) {
                if (x < 10) {
                    write(char('0' + x));
                } else {
                    obuf[por + 0] = '0' + x / 10;
                    obuf[por + 1] = '0' + x % 10;
                    por += 2;
                }
            } else {
                if (x < 1000) {
                    memcpy(obuf + por, pre.num + (x << 2) + 1, 3);
                    por += 3;
                } else {
                    memcpy(obuf + por, pre.num + (x << 2), 4);
                    por += 4;
                }
            }
            memcpy(obuf + por, buf + i + 4, 8 - i);
            por += 8 - i;
        }
    }

    inline int getChar() {
        if (pil + 32 > pir) load();
        return ibuf[pil++]; }

    inline int readChar() {
        if (pil + 32 > pir) load();
        int c = getChar();
        while (c != -1 && c <= 32) c = getChar();
        return c;
    }

    inline void read(char *s) {
        int c = readChar();
        while (c > 32)
            *s++ = c, c = getChar();
        *s = 0;
    }

    inline void read(std::string &s) {
        s.clear();
        int c = readChar();
        while (c > 32) s.push_back(c), c = getChar();
    }

    inline void write(const char *s) {
        while (*s) {
            if (por + 32 > SZ) flush();
            write(*s++);
        }
    }

    inline void write(std::string &s) {
        for (auto &i: s) {
            if (por + 32 > SZ) flush();
            write(i);
        }
    }

    inline void write(double x) {
        if (por + 32 > SZ) flush();
        if (x < 0)
            write('-'), x = -x;
        int t = (int) x;
        write(t), x -= t;
        write('.');
        for (int i = 18 - 1; i > 0; i--) {
            x *= 10;
            t = std::min(9, (int) x);
            write('0' + t), x -= t;
        }
        x *= 10;
        t = std::min(9, (int) (x + 0.5));
        write('0' + t);
    }

    template<typename T, typename ...Args>
    inline void read(T &x, Args &...args) {
        read(x);
        read(args...);
    }

    template<typename T, typename ...Args>
    inline void write(T x, Args ...args) {
        write(x);
        write(args...);
    }

    struct AutoFlush {
        ~AutoFlush() { flush(); }
    } AutoFlush;

}  // namespace fastio
using fastio::read;
using fastio::write;

 
mt19937_64 mt(time(0));
 
void solve();
void init();
 
int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#else
    freopen("input.txt", "r", stdin);
#endif
    init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
 
void init() {}
 
int lovv66;
 
// #define int ll
 
void solve() {
    int h, w;
    // cin >> h >> w;
    read(h, w);
    vector<pair<ll, ll>> a1(h), b1(w), a, b, af, bf, as, bs;
    for (int i = 0; i < h; i++) {
        // cin >> a1[i].x;
        read(a1[i].x);
        a1[i].y = 1;
    }
    for (int i = 0; i < w; i++) {
        // cin >> b1[i].x;
        read(b1[i].x);
        b1[i].y = 1;
    }
    for (int i = 0; i < h; i++) {
        while (a.size() >= 2) {
            auto ff = a.back();
            a.pop_back();
            if (!(a1[i].x <= ff.x && a.back().x <= ff.x)) {
                a.push_back(ff);
                break;
            } else {
                a.back().y += ff.y;
            }
        }
        a.push_back(a1[i]);
    }
    for (int i = 0; i < w; i++) {
        while (b.size() >= 2) {
            auto ff = b.back();
            b.pop_back();
            if (!(b1[i].x <= ff.x && b.back().x <= ff.x)) {
                b.push_back(ff);
                break;
            } else {
                b.back().y += ff.y;
            }
        }
        b.push_back(b1[i]);
    }
    ll ans = 0;
    h = a.size();
    w = b.size();
    af.push_back(a[0]);
    bf.push_back(b[0]);
    for (int i = 1; i < h; i++) {
        if (a[i] > a[i - 1]) {
            as.push_back(a[i]);
        } else {
            af.push_back(a[i]);
        }
    }
    for (int i = 1; i < w; i++) {
        if (b[i] > b[i - 1]) {
            bs.push_back(b[i]);
        } else {
            bf.push_back(b[i]);
        }
    }
    // as.insert(as.begin(), af.back());
    // bs.insert(bs.begin(), bf.back());
    reverse(all(as));
    reverse(all(bs));
    as.push_back(af.back());
    bs.push_back(bf.back());
    for (int i = 0; i < as.size(); i++) {
        as[i].y = as[(i + 1) % as.size()].y;
    }
    for (int i = 0; i < bs.size(); i++) {
        bs[i].y = bs[(i + 1) % bs.size()].y;
    }
    // for (auto i : a) {
    //     cout << i.x << ' ';
    // }
    // cout << '\n';
    // for (auto i : b) {
    //     cout << i.x << ' ';
    // }
    // cout << '\n';
    // for (auto i : af) {
    //     cout << i.x << ' ';
    // }
    // cout << '\n';
    // for (auto i : bf) {
    //     cout << i.x << ' ';
    // }
    // cout << '\n';
    // for (auto i : as) {
    //     cout << i.x << ' ';
    // }
    // cout << '\n';
    // for (auto i : bs) {
    //     cout << i.x << ' ';
    // }
    // cout << '\n';
    // a = af;
    a.clear();
    for (int i = 0; i < af.size(); i++) {
        while (a.size() >= 2) {
            auto ff = a.back();
            a.pop_back();
            if ((ff.x - af[i].x) * a.back().y < (a.back().x - ff.x) * ff.y) {
                a.push_back(ff);
                break;
            } else {
                a.back().y += ff.y;
            }
        }
        a.push_back(af[i]);
    }
    // b = bf;
    b.clear();
    for (int i = 0; i < bf.size(); i++) {
        while (b.size() >= 2) {
            auto ff = b.back();
            b.pop_back();
            if ((ff.x - bf[i].x) * b.back().y < (b.back().x - ff.x) * ff.y) {
                b.push_back(ff);
                break;
            } else {
                b.back().y += ff.y;
            }
        }
        b.push_back(bf[i]);
    }
    h = a.size();
    w = b.size();
    lovv66 = 2.7e8 / h;
    //ll dp[2][100100]{};
    ll ax[100100]{}, bx[100100]{}, ay[100100]{}, by[100100]{};
    // vector<ll> ax(100100), bx(100100), ay(100100), by(100100);
    vector<vector<ll>> dp(2, vector<ll>(100100, INT64_MAX));
    for (int j = 0; j < w + 1; j++) {
        dp[0][j] = INT64_MAX;
    }
    for (int i = 0; i < h; i++) {
        ax[i] = a[i].x;
        ay[i] = a[i].y;
    }
    for (int i = 0; i < w; i++) {
        bx[i] = b[i].x;
        by[i] = b[i].y;
    }
    dp[0][0] = 0;
    // assert(h <= 3e4 && w <= 3e4);
    for (int i = 0; i < h; i++) {
        for (int j = max(0, i - lovv66); j < min(w + 1, i + lovv66 + 10); j++) {
            dp[1][j] = INT64_MAX;
        }
        for (int j = max(0, i - lovv66); j < min(w, i + lovv66); j++) {
            dp[1][j] = min(dp[1][j], dp[0][j] + bx[j] * ay[i]);
            dp[0][j + 1] = min(dp[0][j + 1], dp[0][j] + ax[i] * by[j]);
        }
        swap(dp[0], dp[1]);
    }
    ans += dp[1][w - 1];
    // cout << dp[0][w - 1] << '\n';
    a.clear();
    for (int i = 0; i < as.size(); i++) {
        while (a.size() >= 2) {
            auto ff = a.back();
            a.pop_back();
            if ((ff.x - as[i].x) * a.back().y < (a.back().x - ff.x) * ff.y) {
                a.push_back(ff);
                break;
            } else {
                a.back().y += ff.y;
            }
        }
        a.push_back(as[i]);
    }
    // b = bf;
    b.clear();
    for (int i = 0; i < bs.size(); i++) {
        while (b.size() >= 2) {
            auto ff = b.back();
            b.pop_back();
            if ((ff.x - bs[i].x) * b.back().y < (b.back().x - ff.x) * ff.y) {
                b.push_back(ff);
                break;
            } else {
                b.back().y += ff.y;
            }
        }
        b.push_back(bs[i]);
    }
    h = a.size();
    w = b.size();
    for (int j = 0; j < w + 1; j++) {
        dp[0][j] = INT64_MAX;
    }
    for (int i = 0; i < h; i++) {
        ax[i] = a[i].x;
        ay[i] = a[i].y;
    }
    for (int i = 0; i < w; i++) {
        bx[i] = b[i].x;
        by[i] = b[i].y;
    }
    dp[0][0] = 0;
    lovv66 = 2.7e8 / h;
    // assert(h <= 4e4 && w <= 4e4);
    for (int i = 0; i < h; i++) {
        int l = max(0, i - lovv66), r1 = min(w + 1, i + lovv66 + 1);
        for (int j = l; j < r1; j++) {
            dp[1][j] = INT64_MAX;
        }
        for (int j = l; j < r1 - 1; j++) {
            dp[1][j] = min(dp[1][j], dp[0][j] + bx[j] * ay[i]);
            dp[0][j + 1] = min(dp[0][j + 1], dp[0][j] + ax[i] * by[j]);
        }
        swap(dp[0], dp[1]);
    }
    ans += dp[1][w - 1];
    // cout << dp[0][w - 1] << '\n';
    // cout << ans << '\n';
    write(ans, '\n');
}

Compilation message (stderr)

kyoto.cpp: In function 'void solve()':
kyoto.cpp:329:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  329 |     for (int i = 0; i < as.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:332:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  332 |     for (int i = 0; i < bs.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:361:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  361 |     for (int i = 0; i < af.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:376:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  376 |     for (int i = 0; i < bf.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:422:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  422 |     for (int i = 0; i < as.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:437:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  437 |     for (int i = 0; i < bs.size(); i++) {
      |                     ~~^~~~~~~~~~~

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