Submission #481793

#	Time	Username	Problem	Language	Result	Execution time	Memory
481793		hidden1	Abduction 2 (JOI17_abduction2)	C++14	13 / 100	9 ms	1868 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(ll i = 0; i < n; i ++)
#define revn(i, n) for(ll i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

const ll MAX_N = 1e5 + 10, MAX_LOG = 20;
ll a[MAX_N], b[MAX_N];
ll n, m, q;
map<pair<ll, ll>, ll> dp[4];
ll rmqa[MAX_N][MAX_LOG], rmqb[MAX_N][MAX_LOG];

void prec() {
    forn(i, n) {
        rmqa[i][0] = a[i];
    }
    for(int l = 1; l < MAX_LOG; l ++) {
        forn(i, n) {
            rmqa[i][l] = rmqa[i][l - 1];
            if(i + (1 << (l - 1)) < n) {
                chkmax(rmqa[i][l], rmqa[i + (1 << (l - 1))][l - 1]);
            }
        }
    }

    forn(i, m) {
        rmqb[i][0] = b[i];
    }
    for(int l = 1; l < MAX_LOG; l ++) {
        forn(i, n) {
            rmqb[i][l] = rmqb[i][l - 1];
            if(i + (1 << (l - 1)) < m) {
                chkmax(rmqb[i][l], rmqb[i + (1 << (l - 1))][l - 1]);
            }
        }
    }
}

ll solve(ll x, ll y, ll dir) {
    cerr << x << " " << y << " " << dir << endl;

    if(x < 0 || y < 0 || x >= n || y >= m) {
        while(true) {

        }
    }

    if(dp[dir].find({x, y}) != dp[dir].end()) {
        return dp[dir][{x, y}];
    }

    if(dir == 0) { // Right;
        ll nowCost = a[x];
        cerr << nowCost << endl;
        ll nxt = y;
        revn(l, MAX_LOG) {
            if(nowCost > rmqb[nxt][l]) {
                nxt += (1 << l);
            }
            if(nxt >= m) {
                return dp[dir][{x, y}] = m - 1 - y;
            }
        }
        return dp[dir][{x, y}] = nxt - y + max(solve(x, nxt, 1), solve(x, nxt, 3));
    } else 
    if(dir == 1) { // Down;
        ll nowCost = b[y];
        cerr << nowCost << endl;
        ll nxt = x;
        revn(l, MAX_LOG) {
            if(nowCost > rmqa[nxt][l]) {
                nxt += (1 << l);
            }
            if(nxt >= n) {
                return dp[dir][{x, y}] = n - 1 - x;
            }
        }
        cerr << "going to " << nxt << endl;
        return dp[dir][{x, y}] = nxt - x + max(solve(nxt, y, 0), solve(nxt, y, 2));
    } else 
    if(dir == 2) { // Left;
        ll nowCost = a[x];
        cerr << nowCost << endl;
        ll nxt = y;
        revn(l, MAX_LOG) {
            if(nxt - (1 << l) + 1 < 0) {continue;}
            if(nowCost > rmqb[nxt - (1 << l) + 1][l]) {
                nxt -= (1 << l);
            }
            if(nxt < 0) {
                return dp[dir][{x, y}] = y;
            }
        }
        return dp[dir][{x, y}] = y - nxt + max(solve(x, nxt, 1), solve(x, nxt, 3));
    } else 
    if(dir == 3) { // Up;
        ll nowCost = b[y];
        cerr << nowCost << endl;
        ll nxt = x;
        revn(l, MAX_LOG) {
            if(nxt - (1 << l) + 1 < 0) {continue;}
            if(nowCost > rmqa[nxt - (1 << l) + 1][l]) {
                nxt -= (1 << l);
            }
            if(nxt < 0) {
                return dp[dir][{x, y}] = x;
            }
        }
        return dp[dir][{x, y}] = x - nxt + max(solve(nxt, y, 2), solve(nxt, y, 0));
    } 
}

signed main() {
    // ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> q;
    forn(i, n) {
        cin >> a[i];
    }
    forn(i, m) {
        cin >> b[i];
    }   
    prec();

    while(q --) {
        ll x, y;
        cin >> x >> y;
        x --;
        y --;
        ll ret = 0;
        if(x != n - 1) {
            chkmax(ret, solve(x + 1, y, 1));
        }
        if(x != 0) {
            chkmax(ret, solve(x - 1, y, 3));
        }
        if(y != m - 1) {
            chkmax(ret, solve(x, y + 1, 0));
        }
        if(y != 0) {
            chkmax(ret, solve(x, y - 1, 2));
        }
        cout << ret + 1 << endl;
    }

    return 0;

    forn(dir, 4) {
        cout << dir << endl;
        for(auto it : dp[dir]) {
            cout << "[" << it.first << "] " << it.second << endl;
        }
    }

    return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'll solve(ll, ll, ll)':
abduction2.cpp:125:1: warning: control reaches end of non-void function [-Wreturn-type]
  125 | }
      | ^

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