Submission #1044662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044662		juicy	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	422 ms	137556 KiB

abduction2

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e4 + 5, LG = 16;

int n, m, q;
int a[N], b[N], spt[2][LG][N], lg[N];
map<int, long long> mp[2][N];

void bld(int spt[LG][N], int *A, int n) {
    for (int i = 1; i <= n; ++i) {
        spt[0][i] = A[i];
    }
    for (int j = 1; j <= lg[n]; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            spt[j][i] = max(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
        }
    }
}

int qry(int spt[LG][N], int l, int r) {
    int k = lg[r - l + 1];
    return max(spt[k][l], spt[k][r - (1 << k) + 1]);
}

int prv(int spt[LG][N], int i, int x) {
    int l = 1, r = i - 1, res = 0;
    while (l <= r) {
        int md = (l + r) / 2;
        if (qry(spt, md, i - 1) > x) {
            res = md;
            l = md + 1;
        } else {
            r = md - 1;
        }
    }
    return res;
}

int nxt(int spt[LG][N], int i, int n, int x) {
    int l = i + 1, r = n, res = n + 1;
    while (l <= r) {
        int md = (l + r) / 2;
        if (qry(spt, i + 1, md) > x) {
            res = md;
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    return res;
}

long long solve(int i, int j, int dr) {
    if (mp[dr][i].count(j)) {
        return mp[dr][i][j];
    }
    long long res = 0;
    if (dr == 0) {
        int lt = prv(spt[1], j, a[i]), rt = nxt(spt[1], j, m, a[i]);
        res = max({res, lt == 0 ? j - 1 : solve(i, lt, 1) + j - lt, rt == m + 1 ? m - j : solve(i, rt, 1) + rt - j}); 
    } else {
        int lt = prv(spt[0], i, b[j]), rt = nxt(spt[0], i, n, b[j]);
        res = max({res, lt == 0 ? i - 1 : solve(lt, j, 0) + i - lt, rt == n + 1 ? n - i : solve(rt, j, 0) + rt - i});
    }
    return mp[dr][i][j] = res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 2; i <= max(n, m); ++i) {
        lg[i] = lg[i / 2] + 1;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }    
    for (int i = 1; i <= m; ++i) {
        cin >> b[i];
    }
    bld(spt[0], a, n);
    bld(spt[1], b, m);
    while (q--) {
        int s, t; cin >> s >> t;
        cout << max(solve(s, t, 0), solve(s, t, 1)) << "\n";
    }
    return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'void bld(int (*)[50005], int*, int)':
abduction2.cpp:23:67: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |             spt[j][i] = max(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                                 ~~^~~

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