oj.uz

Submission #481793

# Submission time Handle Problem Language Result Execution time Memory
481793 2021-10-21T23:37:29 Z hidden1 Abduction 2 (JOI17_abduction2) C++14
13 / 100
 9 ms 1868 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 956 KB Output is correct
14 Correct 2 ms 972 KB Output is correct
15 Correct 2 ms 972 KB Output is correct
16 Correct 2 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 4 ms 1356 KB Output is correct
20 Incorrect 6 ms 1484 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 956 KB Output is correct
14 Correct 2 ms 972 KB Output is correct
15 Correct 2 ms 972 KB Output is correct
16 Correct 2 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 4 ms 1356 KB Output is correct
20 Incorrect 6 ms 1484 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1356 KB Output is correct
2 Correct 5 ms 1340 KB Output is correct
3 Correct 5 ms 1356 KB Output is correct
4 Correct 5 ms 1356 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 4 ms 1356 KB Output is correct
7 Correct 4 ms 1356 KB Output is correct
8 Correct 9 ms 1868 KB Output is correct
9 Incorrect 9 ms 1768 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 956 KB Output is correct
14 Correct 2 ms 972 KB Output is correct
15 Correct 2 ms 972 KB Output is correct
16 Correct 2 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 4 ms 1356 KB Output is correct
20 Incorrect 6 ms 1484 KB Output isn't correct
21 Halted 0 ms 0 KB -