oj.uz

답안 #282226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
282226 2020-08-24T07:19:41 Z 반딧불(#5757) 유괴 2 (JOI17_abduction2) C++17
13 / 100
 6 ms 1024 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll ctd(int x, int y, int d){
    return 10000000000LL*d + 100000LL*x + y;
}

struct segTree{
    int tree[200002];
    void initialize(int i, int l, int r, int A[]){
        if(l==r){
            tree[i] = A[l];
            return;
        }
        int m = (l+r)>>1;
        initialize(i*2, l, m, A), initialize(i*2+1, m+1, r, A);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
    int findMinIdx(int i, int l, int r, int s, int val){
        if(r <= s) return -1;
        if(tree[i] <= val) return -1;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = findMinIdx(i*2, l, m, s, val);
        if(tmp != -1) return tmp;
        return findMinIdx(i*2+1, m+1, r, s, val);
    }
    int findMaxIdx(int i, int l, int r, int e, int val){
        if(l >= e) return -1;
        if(tree[i] <= val) return -1;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = findMaxIdx(i*2+1, m+1, r, e, val);
        if(tmp != -1) return tmp;
        return findMaxIdx(i*2, l, m, e, val);
    }
} tree1, tree2;

int n, m, q;
int arr1[50002], arr2[50002];
ll ans;
unordered_map<ll, ll> DP;

/// ����: 0: up, 1: right, 2: down, 3: left
ll getAns(int x, int y, int d){
    if(DP.find(ctd(x, y, d)) != DP.end()) return DP[ctd(x, y, d)];
    int val;
    ll idx = ctd(x, y, d);
    switch(d){
    case 0: /// ���� ����. tree1���� ���� �۾��� �ʿ��ϴ�.
        val = tree1.findMaxIdx(1, 1, n, x, arr2[y]);
        if(val == -1) DP[idx] = x-1;
        else DP[idx] = (x-val) + max(getAns(val, y, 1), getAns(val, y, 3));
        break;
    case 2: /// �Ʒ��� ����. tree1���� ���� �۾��� �ʿ��ϴ�.
        val = tree1.findMinIdx(1, 1, n, x, arr2[y]);
        if(val == -1) DP[idx] = n-x;
        else DP[idx] = (val-x) + max(getAns(val, y, 1), getAns(val, y, 3));
        break;
    case 3: /// �������� ����. tree2���� ���� �۾��� �ʿ��ϴ�.
        val = tree2.findMaxIdx(1, 1, m, y, arr1[x]);
        if(val == -1) DP[idx] = y-1;
        else DP[idx] = (y-val) + max(getAns(x, val, 0), getAns(x, val, 2));
        break;
    case 1: /// ���������� ����. tree2���� ���� �۾��� �ʿ��ϴ�.
        val = tree2.findMinIdx(1, 1, m, y, arr1[x]);
        if(val == -1) DP[idx] = n-y;
        else DP[idx] = (val-y) + max(getAns(x, val, 0), getAns(x, val, 2));
        break;
    }
    return DP[idx];
}
int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr1[i]);
    }
    for(int i=1; i<=m; i++){
        scanf("%d", &arr2[i]);
    }
    tree1.initialize(1, 1, n, arr1);
    tree2.initialize(1, 1, m, arr2);

    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        ans = 0;
        for(int d=0; d<4; d++){
            ans = max(ans, getAns(x, y, d));
        }
        printf("%lld\n", ans);
    }
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         scanf("%d", &arr1[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         scanf("%d", &arr2[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 4 ms 896 KB Output is correct
21 Incorrect 4 ms 768 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 4 ms 896 KB Output is correct
21 Incorrect 4 ms 768 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Incorrect 5 ms 1024 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 4 ms 896 KB Output is correct
21 Incorrect 4 ms 768 KB Output isn't correct
22 Halted 0 ms 0 KB -