Submission #699095

#	Time	Username	Problem	Language	Result	Execution time	Memory
699095		tengiz05	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	1258 ms	93356 KiB

abduction2

#include <bits/stdc++.h>

using i64 = long long;

constexpr int Log = 16;
constexpr int N = 50000;
int am[Log][N], bm[Log][N];

void chmax(i64 &a, i64 b) {
    if (a < b)
        a = b;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, q;
    std::cin >> n >> m >> q;
    
    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
    }
    
    for (int i = 0; i < n; i++)
        am[0][i] = a[i];
    for (int j = 0; (1 << (j + 1)) <= n; j++)
        for (int i = 0; i + (1 << (j + 1)) <= n; i++)
            am[j + 1][i] = std::max(am[j][i], am[j][i + (1 << j)]);
    for (int i = 0; i < m; i++)
        bm[0][i] = b[i];
    for (int j = 0; (1 << (j + 1)) <= m; j++)
        for (int i = 0; i + (1 << (j + 1)) <= m; i++)
            bm[j + 1][i] = std::max(bm[j][i], bm[j][i + (1 << j)]);
    
    std::unordered_map<i64, i64> dp;
    std::function<i64(int, int, int)> calc = [&](int x, int y, int t) {
        i64 state = x * 1LL * m + y + t * (1LL << 60);
        if (dp.count(state))
            return dp[state];
        i64 res = 0;
        if (t == 0) {
            int j = y + 1;
            for (int k = Log - 1; k >= 0; k--)
                if (j + (1 << k) <= m && bm[k][j] <= a[x])
                    j += 1 << k;
            if (j == m)
                chmax(res, m - 1 - y);
            else
                chmax(res, j - y + calc(x, j, !t));
            j = y;
            for (int k = Log - 1; k >= 0; k--)
                if (j - (1 << k) >= 0 && bm[k][j - (1 << k)] <= a[x])
                    j -= 1 << k;
            j--;
            if (j == -1)
                chmax(res, y);
            else
                chmax(res, y - j + calc(x, j, !t));
        } else {
            int i = x + 1;
            for (int k = Log - 1; k >= 0; k--)
                if (i + (1 << k) <= n && am[k][i] <= b[y])
                    i += 1 << k;
            if (i == n)
                chmax(res, n - 1 - x);
            else
                chmax(res, i - x + calc(i, y, !t));
            i = x;
            for (int k = Log - 1; k >= 0; k--)
                if (i - (1 << k) >= 0 && am[k][i - (1 << k)] <= b[y])
                    i -= 1 << k;
            i--;
            if (i == -1)
                chmax(res, x);
            else
                chmax(res, x - i + calc(i, y, !t));
        }
        return dp[state] = res;
    };
    
    while (q--) {
        int s, t;
        std::cin >> s >> t;
        s--;
        t--;
        std::cout << std::max(calc(s, t, 0), calc(s, t, 1)) << "\n";
    }
    
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56