oj.uz

Submission #241185

# Submission time Handle Problem Language Result Execution time Memory
241185 2020-06-23T08:27:31 Z osaaateiasavtnl Abduction 2 (JOI17_abduction2) C++17
27 / 100
 1976 ms 524292 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1e5+7;

int a[N], b[N];

struct State {
    int x, y, t;
    int val() {
        if (t&1)
            return a[x];
        else
            return b[y];
    };
    bool operator <(State s) {
        return val() < s.val();
    }
};  

int n, m, q;
map <int, int> dp[4][N];
int get(int x, int y, int t) {
    if (x < 0 || x >= n || y < 0 || y >= m) 
        return -1;

    if (dp[t][x].find(y) != dp[t][x].end())
        return dp[t][x][y];

    int &d = dp[t][x][y];
    d = 0;

    if (t&1) {
        if (a[x] < b[y]) {
            d = max(d, get(x,y,0));
            d = max(d, get(x,y,2));
        }
        else if (t == 1) {
            if (y + 1 < m)
                d = get(x,y+1,1)+1;
        }   
        else {
            if (y) 
                d = get(x,y-1,3)+1;
        }   
    }   
    else {
        if (b[y] < a[x]) {
            d = max(d, get(x,y,1));
            d = max(d, get(x,y,3));
        }   
        else if (t == 0) {
            if (x)
                d = get(x-1,y,0)+1;
        }
        else {
            if (x + 1 < n) 
                d = get(x+1,y,2)+1;
        }   
    }

    return d;
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    cin >> n >> m >> q;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < m; ++i)
        cin >> b[i];
    
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        int ans = 0;
        ans = max(ans, get(x-1,y,0)+1);
        ans = max(ans, get(x+1,y,2)+1);
        ans = max(ans, get(x,y-1,3)+1);
        ans = max(ans, get(x,y+1,1)+1);
        cout << ans << endl;
    }   
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19072 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 15 ms 19200 KB Output is correct
4 Correct 15 ms 19200 KB Output is correct
5 Correct 15 ms 19200 KB Output is correct
6 Correct 15 ms 19072 KB Output is correct
7 Correct 15 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 15 ms 19072 KB Output is correct
10 Correct 17 ms 19072 KB Output is correct
11 Correct 15 ms 19072 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19072 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 15 ms 19200 KB Output is correct
4 Correct 15 ms 19200 KB Output is correct
5 Correct 15 ms 19200 KB Output is correct
6 Correct 15 ms 19072 KB Output is correct
7 Correct 15 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 15 ms 19072 KB Output is correct
10 Correct 17 ms 19072 KB Output is correct
11 Correct 15 ms 19072 KB Output is correct
12 Correct 16 ms 19584 KB Output is correct
13 Correct 17 ms 19712 KB Output is correct
14 Correct 20 ms 19584 KB Output is correct
15 Correct 17 ms 19584 KB Output is correct
16 Correct 21 ms 19712 KB Output is correct
17 Correct 25 ms 22784 KB Output is correct
18 Correct 110 ms 44284 KB Output is correct
19 Correct 582 ms 176216 KB Output is correct
20 Correct 717 ms 220196 KB Output is correct
21 Correct 597 ms 192760 KB Output is correct
22 Correct 1435 ms 366072 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19072 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 15 ms 19200 KB Output is correct
4 Correct 15 ms 19200 KB Output is correct
5 Correct 15 ms 19200 KB Output is correct
6 Correct 15 ms 19072 KB Output is correct
7 Correct 15 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 15 ms 19072 KB Output is correct
10 Correct 17 ms 19072 KB Output is correct
11 Correct 15 ms 19072 KB Output is correct
12 Correct 16 ms 19584 KB Output is correct
13 Correct 17 ms 19712 KB Output is correct
14 Correct 20 ms 19584 KB Output is correct
15 Correct 17 ms 19584 KB Output is correct
16 Correct 21 ms 19712 KB Output is correct
17 Correct 25 ms 22784 KB Output is correct
18 Correct 110 ms 44284 KB Output is correct
19 Correct 582 ms 176216 KB Output is correct
20 Correct 717 ms 220196 KB Output is correct
21 Correct 597 ms 192760 KB Output is correct
22 Correct 1435 ms 366072 KB Output is correct
23 Correct 63 ms 31736 KB Output is correct
24 Correct 93 ms 40952 KB Output is correct
25 Correct 82 ms 36756 KB Output is correct
26 Correct 89 ms 44408 KB Output is correct
27 Correct 62 ms 32760 KB Output is correct
28 Runtime error 1976 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 25464 KB Output is correct
2 Correct 41 ms 25208 KB Output is correct
3 Correct 40 ms 25848 KB Output is correct
4 Correct 39 ms 25848 KB Output is correct
5 Correct 39 ms 25976 KB Output is correct
6 Correct 434 ms 125560 KB Output is correct
7 Correct 383 ms 126176 KB Output is correct
8 Correct 923 ms 267952 KB Output is correct
9 Correct 894 ms 259708 KB Output is correct
10 Correct 893 ms 256404 KB Output is correct
11 Correct 1561 ms 394648 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19072 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 15 ms 19200 KB Output is correct
4 Correct 15 ms 19200 KB Output is correct
5 Correct 15 ms 19200 KB Output is correct
6 Correct 15 ms 19072 KB Output is correct
7 Correct 15 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 15 ms 19072 KB Output is correct
10 Correct 17 ms 19072 KB Output is correct
11 Correct 15 ms 19072 KB Output is correct
12 Correct 16 ms 19584 KB Output is correct
13 Correct 17 ms 19712 KB Output is correct
14 Correct 20 ms 19584 KB Output is correct
15 Correct 17 ms 19584 KB Output is correct
16 Correct 21 ms 19712 KB Output is correct
17 Correct 25 ms 22784 KB Output is correct
18 Correct 110 ms 44284 KB Output is correct
19 Correct 582 ms 176216 KB Output is correct
20 Correct 717 ms 220196 KB Output is correct
21 Correct 597 ms 192760 KB Output is correct
22 Correct 1435 ms 366072 KB Output is correct
23 Correct 63 ms 31736 KB Output is correct
24 Correct 93 ms 40952 KB Output is correct
25 Correct 82 ms 36756 KB Output is correct
26 Correct 89 ms 44408 KB Output is correct
27 Correct 62 ms 32760 KB Output is correct
28 Runtime error 1976 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -