oj.uz

Submission #699091

# Submission time Handle Problem Language Result Execution time Memory
699091 2023-02-15T15:10:53 Z tengiz05 Abduction 2 (JOI17_abduction2) C++17
13 / 100
 5000 ms 820 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int Log = 16;
constexpr int N = 50000;
int am[Log][N], bm[Log][N];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, q;
    std::cin >> n >> m >> q;
    
    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
    }
    
    for (int i = 0; i < n; i++)
        am[0][i] = a[i];
    for (int j = 0; (1 << (j + 1)) <= n; j++)
        for (int i = 0; i + (1 << (j + 1)) <= n; i++)
            am[j + 1][i] = std::max(am[j][i], am[j][i + (1 << j)]);
    for (int i = 0; i < m; i++)
        bm[0][i] = b[i];
    for (int j = 0; (1 << (j + 1)) <= m; j++)
        for (int i = 0; i + (1 << (j + 1)) <= m; i++)
            bm[j + 1][i] = std::max(bm[j][i], bm[j][i + (1 << j)]);
    
    std::function<int(int, int, int)> calc = [&](int x, int y, int t) {
        int res = 0;
        if (t == 0) {
            int j = y + 1;
            for (int k = Log - 1; k >= 0; k--)
                if (j + (1 << k) <= m && bm[k][j] <= a[x])
                    j += 1 << k;
            if (j == m)
                res = std::max(res, m - 1 - y);
            else
                res = std::max(res, j - y + calc(x, j, !t));
            j = y;
            for (int k = Log - 1; k >= 0; k--)
                if (j - (1 << k) >= 0 && bm[k][j - (1 << k)] <= a[x])
                    j -= 1 << k;
            j--;
            if (j == -1)
                res = std::max(res, y);
            else
                res = std::max(res, y - j + calc(x, j, !t));
        } else {
            int i = x + 1;
            for (int k = Log - 1; k >= 0; k--)
                if (i + (1 << k) <= n && am[k][i] <= b[y])
                    i += 1 << k;
            if (i == n)
                res = std::max(res, n - 1 - x);
            else
                res = std::max(res, i - x + calc(i, y, !t));
            i = x;
            for (int k = Log - 1; k >= 0; k--)
                if (i - (1 << k) >= 0 && am[k][i - (1 << k)] <= b[y])
                    i -= 1 << k;
            i--;
            if (i == -1)
                res = std::max(res, x);
            else
                res = std::max(res, x - i + calc(i, y, !t));
        }
        return res;
    };
    
    while (q--) {
        int s, t;
        std::cin >> s >> t;
        s--;
        t--;
        std::cout << std::max(calc(s, t, 0), calc(s, t, 1)) << "\n";
    }
    
    return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Execution timed out 5052 ms 596 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Execution timed out 5052 ms 596 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 716 KB Output is correct
2 Correct 12 ms 632 KB Output is correct
3 Correct 15 ms 596 KB Output is correct
4 Correct 16 ms 596 KB Output is correct
5 Correct 17 ms 636 KB Output is correct
6 Correct 23 ms 772 KB Output is correct
7 Correct 20 ms 820 KB Output is correct
8 Execution timed out 5061 ms 596 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Execution timed out 5052 ms 596 KB Time limit exceeded
20 Halted 0 ms 0 KB -