Submission #1168620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168620		OI_Account	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	1469 ms	141292 KiB

abduction2

#pragma GCC optimize("O2,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 50000;
const int M = 16;

int n[2], q, a[2][N + 10];
ll mx[2][N + 10][M + 3];

void readInput() {
    cin >> n[0] >> n[1] >> q;
    for (int t = 0; t < 2; t++)
        for (int i = 1; i <= n[t]; i++)
            cin >> a[t][i];
}

void calcRMQ() {
    for (int t = 0; t < 2; t++) {
        for (int i = 1; i <= n[t]; i++)
            mx[t][i][0] = a[t][i];
        for (int j = 1; j <= M; j++)
            for (int i = 1; i + (1 << j) - 1 <= n[t]; i++)
                mx[t][i][j] = max(mx[t][i][j - 1], mx[t][i + (1 << (j - 1))][j - 1]);
    }
}

int getMax(int t, int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    return max(mx[t][l][lg], mx[t][r - (1 << lg) + 1][lg]);
}

int getLeft(int t, int i, int x) {
    int l = 0, r = i;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (getMax(t, mid, i - 1) > x)
            l = mid;
        else
            r = mid;
    }
    return l;
}

int getRight(int t, int i, int x) {
    int l = i, r = n[t] + 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (getMax(t, i + 1, mid) > x)
            r = mid;
        else
            l = mid;
    }
    return r;
}

map<pair<int, pair<int, int>>, ll> mp;

ll calcDP(int t, int i, int j) {
    if (mp[{t, {i, j}}])
        return mp[{t, {i, j}}] - 1;
    int idx[2] = {i, j};
    int x = a[1 - t][idx[1 - t]];
    int l = getLeft(t, idx[t], x);
    ll case1;
    if (l == 0)
        case1 = idx[t] - 1;
    else {
        case1 = (t == 0? calcDP(1, l, idx[1]): calcDP(0, idx[0], l));
        case1 += idx[t] - l;
    }
    int r = getRight(t, idx[t], x);
    ll case2;
    if (r == n[t] + 1)
        case2 = r - idx[t] - 1;
    else {
        case2 = (t == 0? calcDP(1, r, idx[1]): calcDP(0, idx[0], r));
        case2 += r - idx[t];
    }
    mp[{t, {i, j}}] = max(case1, case2) + 1;
    return max(case1, case2);
}

void calcDP() {
    vector<pair<pair<int, int>, pair<int, int>>> vec;
    for (int i = 1; i <= n[0]; i++)
        for (int j = 1; j <= n[1]; j++) {
            vec.push_back({{a[1][j], 0}, {i, j}});
            vec.push_back({{a[0][i], 1}, {i, j}});
        }
    sort(vec.begin(), vec.end());
    for (int i = (int) vec.size() - 1; i >= 0; i--)
        calcDP(vec[i].first.second, vec[i].second.first, vec[i].second.second);
}

void query() {
    int x, y;
    cin >> x >> y;
    cout << max(calcDP(0, x, y), calcDP(1, x, y)) << '\n';
}

void solve() {
    while (q--)
        query();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcRMQ();
    solve();
    return 0;
}

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