Submission #1268001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268001		M_W_13	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	2108 ms	127216 KiB

abduction2

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define pll pair<ll, ll>
const int MAXN = 1 << 17;
int N = 1;
int seg[MAXN][2];
int T[MAXN][2];
int n, m, q;

int szuk(int v, int c, int x, bool odwroc) {
    if (v >= N) {
        return (v - N);
    }
    if (odwroc) {
        if (seg[2 * v + 1][c] > x) {
            return szuk(2 * v + 1, c, x, odwroc);
        }
        return szuk(2 * v, c, x, odwroc);    
    }
    


    if (seg[2 * v][c] > x) {
        return szuk(2 * v, c, x, odwroc);
    }
    return szuk(2 * v + 1, c, x, odwroc);
}

int query(int l, int r, int c, int x, bool odwroc) {
    l += N;
    r += N;
    vector<int> vec1;
    vector<int> vec2;
    while (l <= r) {
        if (l % 2 == 1) {
            if (seg[l][c] > x) {
                vec1.pb(l);
            }
            l++;
        }
        if (r % 2 == 0) {
            if (seg[r][c] > x) {
                vec2.pb(r);
            }
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (odwroc) {
        reverse(vec1.begin(), vec1.end());
        reverse(vec2.begin(), vec2.end());
        if (!vec2.empty()) {
            int sz = vec2.size();
            return szuk(vec2[sz - 1], c, x, odwroc);
        }
        if (!vec1.empty()) {
            return szuk(vec1[0], c, x, odwroc);
        }
        return -1;
    }
    if (!vec1.empty()) {
        return szuk(vec1[0], c, x, odwroc);
    }
    if (!vec2.empty()) {
        int sz = vec2.size();
        return szuk(vec2[sz - 1], c, x, odwroc);
    }
    return -1;
}

map<pair<pii, bool>, ll> ans;

void licz(int a, int b, bool c) {
    pair<pii, bool> p = {{a, b}, c};
    if (ans.find(p) != ans.end()) {
        return ;
    }
    if (c) {
        int x1 = -1;
        int x2 = -1;
        if (a > 0) {
            x1 = query(0, a - 1, c, T[b][c], 1);
        }
        if (a < n - 1) {
            x2 = query(a + 1, n - 1, c, T[b][c], 0);
        }
        // cout << "a = " << a << " b = " << b << " x1 = " << x1 << " x2 = " << x2 << " val = " << T[b][c] << '\n';
        ans[p] = 0;
        if (x1 != -1) {
            licz(x1, b, c ^ 1);
            ans[p] = max(ans[p], (long long)a - x1 + ans[{{x1, b}, c ^ 1}]);
        }
        else {
            ans[p] = max(ans[p], (long long)a);
        }
        if (x2 != -1) {
            licz(x2, b, c ^ 1);
            ans[p] = max(ans[p], (long long)x2 - a + ans[{{x2, b}, c ^ 1}]);
        }
        else {
            ans[p] = max(ans[p], (long long)n - 1 - a);
        }
    }
    else {
        int y1 = -1;
        int y2 = -1;
        if (b > 0) {
            y1 = query(0, b - 1, c, T[a][c], 1);
        }
        if (b < m - 1) {
            y2 = query(b + 1, m - 1, c, T[a][c], 0);
        }
        // cout << "a = " << a << " b = " << b << " y1 = " << y1 << " y2 = " << y2 << '\n';
        ans[p] = 0;
        if (y1 != -1) {
            licz(a, y1, c ^ 1);
            ans[p] = max(ans[p], (long long)b - y1 + ans[{{a, y1}, c ^ 1}]);
        }
        else {
            ans[p] = max(ans[p], (long long)b);
        }
        if (y2 != -1) {
            licz(a, y2, c ^ 1);
            ans[p] = max(ans[p], (long long)y2 - b + ans[{{a, y2}, c ^ 1}]);
        }
        else {
            ans[p] = max(ans[p], (long long)m - 1 - b);
        }
    }
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    while (N < n) N *= 2;
    rep(i, n) {
        cin >> T[i][0];
        seg[i + N][1] = T[i][0];
    }
    rep(i, m) {
        cin >> T[i][1];
        seg[i + N][0] = T[i][1];
    }
    for (int i = N - 1; i >= 1; i--) {
        rep(c, 2) {
            seg[i][c] = max(seg[2 * i][c], seg[2 * i + 1][c]);
        }
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        licz(x, y, 0);
        licz(x, y, 1);
        // cout << ans[{{x, y}, 0}] << " " << ans[{{x, y}, 1}] << '\n';
        cout << max(ans[{{x, y}, 0}], ans[{{x, y}, 1}]) << '\n';
    }
	return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'void licz(int, int, bool)':
abduction2.cpp:99:70: warning: narrowing conversion of '(((int)c) ^ 1)' from 'int' to 'bool' [-Wnarrowing]
   99 |             ans[p] = max(ans[p], (long long)a - x1 + ans[{{x1, b}, c ^ 1}]);
      |                                                                    ~~^~~
abduction2.cpp:106:70: warning: narrowing conversion of '(((int)c) ^ 1)' from 'int' to 'bool' [-Wnarrowing]
  106 |             ans[p] = max(ans[p], (long long)x2 - a + ans[{{x2, b}, c ^ 1}]);
      |                                                                    ~~^~~
abduction2.cpp:125:70: warning: narrowing conversion of '(((int)c) ^ 1)' from 'int' to 'bool' [-Wnarrowing]
  125 |             ans[p] = max(ans[p], (long long)b - y1 + ans[{{a, y1}, c ^ 1}]);
      |                                                                    ~~^~~
abduction2.cpp:132:70: warning: narrowing conversion of '(((int)c) ^ 1)' from 'int' to 'bool' [-Wnarrowing]
  132 |             ans[p] = max(ans[p], (long long)y2 - b + ans[{{a, y2}, c ^ 1}]);
      |                                                                    ~~^~~

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