Submission #1156765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156765		jerzyk	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	2455 ms	126064 KiB

abduction2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 50'007;
int tab[2][N];
map<pair<int, int>, ll> ans;

int GetL(int r, int a, int x)
{
    while(tab[r][a] <= x)
        --a;
    return a;
}

int GetR(int r, int a, int x)
{
    while(tab[r][a] <= x)
        ++a;
    return a;
}

ll F(int n, int m, int i, int j)
{
    if(ans.find(make_pair(i, j)) != ans.end())
        return ans[make_pair(i, j)];
    if(i == 0 || j == 0 || i > n || j > m) return 0;
    int a, b;
    ll answer = 0LL;
    if(tab[0][i] > tab[1][j])
    {
        a = GetL(1, j, tab[0][i]);
        b = GetR(1, j, tab[0][i]);
        answer = max(F(n, m, i, a) + (ll)(j - a), F(n, m, i, b) + (ll)(b - j));
    }else
    {
        a = GetL(0, i, tab[1][j]);
        b = GetR(0, i, tab[1][j]);
        answer = max(F(n, m, a, j) + (ll)(i - a), F(n, m, b, j) + (ll)(b - i));
    }
    ans[make_pair(i, j)] = answer;
    return answer;
}

inline ll Q(int n, int m, int i, int j)
{
    ll a1, a2;
    int a, b;
    a = GetL(1, j - 1 , tab[0][i]);
    b = GetR(1, j + 1, tab[0][i]);
    a1 = max(F(n, m, i, a) + (ll)(j - a), F(n, m, i, b) + (ll)(b - j)) - 1LL;

    a = GetL(0, i - 1, tab[1][j]);
    b = GetR(0, i + 1, tab[1][j]);
    a2 = max(F(n, m, a, j) + (ll)(i - a), F(n, m, b, j) + (ll)(b - i)) - 1LL;

    return max(a1, a2);
}

void Solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    tab[0][0] = II; tab[0][n + 1] = II;
    tab[1][0] = II; tab[1][m + 1] = II;
    for(int i = 1; i <= n; ++i)
        cin >> tab[0][i];
    for(int j = 1; j <= m; ++j)
        cin >> tab[1][j];
    int a, b;
    for(int i = 1; i <= q; ++i)
    {
        cin >> a >> b;
        cout << Q(n, m, a, b) << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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