Submission #1261653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261653		patgra	Abduction 2 (JOI17_abduction2)	C++20	100 / 100	1796 ms	234652 KiB

abduction2

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int tB, h, w, q;
vector<array<int, 2>> t;

struct hsh {
    ll operator() (pair<int, int> x) const {
        return (((ll)x.first) << 32) | x.second;
    }
};
array<unordered_map<pair<int, int>, ll, hsh>, 4> mp;

int findNextGr(int i, int tn, int x) {
    int v = i + tB;
    while(v > 1) {
        if(v % 2 == 0) if(t[v + 1][tn] > x) { v++; break; }
        v /= 2;
    }
    if(v <= 1) return -1;
    while(v < tB) v *= 2, v += t[v][tn] <= x;
    return v - tB;
}

int findPrevGr(int i, int tn, int x) {
    int v = i + tB;
    while(v > 1) {
        if(v % 2 == 1) if(t[v - 1][tn] > x) { v--; break; }
        v /= 2;
    }
    if(v <= 1) return -1;
    while(v < tB) v = v * 2 + 1, v -= t[v][tn] <= x;
    return v - tB;
}

ll calcIt(int x, int y, int dir) {
    if(mp[dir].count({x, y})) return mp[dir][{x, y}];
    if(dir == 0) {
        auto x2 = findPrevGr(x, 0, t[tB + y][1]);
        if(x2 == -1) mp[dir][{x, y}] = x;
        else mp[dir][{x, y}] = max(calcIt(x2, y, 1), calcIt(x2, y, 3)) + x - x2;
    }
    if(dir == 1) {
        auto y2 = findPrevGr(y, 1, t[tB + x][0]);
        if(y2 == -1) mp[dir][{x, y}] = y;
        else mp[dir][{x, y}] = max(calcIt(x, y2, 0), calcIt(x, y2, 2)) + y - y2;
    }
    if(dir == 2) {
        auto x2 = findNextGr(x, 0, t[tB + y][1]);
        if(x2 == -1) mp[dir][{x, y}] = h - x - 1; 
        else mp[dir][{x, y}] = max(calcIt(x2, y, 1), calcIt(x2, y, 3)) + x2 - x;
    }
    if(dir == 3) {
        auto y2 = findNextGr(y, 1, t[tB + x][0]);
        if(y2 == -1) mp[dir][{x, y}] = w - y - 1;
        else mp[dir][{x, y}] = max(calcIt(x, y2, 0), calcIt(x, y2, 2)) + y2 - y;
    }
    return mp[dir][{x, y}];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> h >> w >> q;
    tB = 1 << (32 - __builtin_clz(max(h, w)));
    t.resize(2 * tB, {-1, -1});
    rep(i, 0, h) cin >> t[tB + i][0];
    rep(i, 0, w) cin >> t[tB + i][1];
    repD(i, tB - 1, 0) rep(j, 0, 2) t[i][j] = max(t[2 * i][j], t[2 * i + 1][j]);
    rep(i, 0, q) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        ll ans = 0;
        rep(j, 0, 4) ans = max(ans, calcIt(x, y, j));
        cout << ans << '\n';
    }
    return 0;
}

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