oj.uz

답안 #195514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
195514 2020-01-16T08:13:10 Z stefdasca 유괴 2 (JOI17_abduction2) C++14
13 / 100
 2011 ms 1244 KB 
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
int h, w, q, vh[50002], vw[50002];
int aint[200002], aint2[200002];
void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = vh[st];
        return;
    }
    int mid = (st + dr) / 2;
    build(nod << 1, st, mid);
    build(nod << 1|1, mid+1, dr);
    aint[nod] = max(aint[nod << 1], aint[nod << 1|1]);
}
void build2(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint2[nod] = vw[st];
        return;
    }
    int mid = (st + dr) / 2;
    build2(nod << 1, st, mid);
    build2(nod << 1|1, mid+1, dr);
    aint2[nod] = max(aint2[nod << 1], aint2[nod << 1|1]);
}
int val;
int query(int nod, int st, int dr, int L, int R)
{
    if(L > R)
        return -1;
    if(dr < L || st > R)
        return -1;
    if(aint[nod] <= val)
        return -1;
    if(st == dr)
        return st;
    int mid = (st + dr) / 2;
    int ans = query(nod << 1|1, mid+1, dr, L, R);
    if(ans != -1)
        return ans;
    return query(nod << 1, st, mid, L, R);
}
int query2(int nod, int st, int dr, int L, int R)
{
    if(L > R)
        return -1;
    if(dr < L || st > R)
        return -1;
    if(aint[nod] <= val)
        return -1;
    if(st == dr)
        return st;
    int mid = (st + dr) / 2;
    int ans = query2(nod << 1, st, mid, L, R);
    if(ans != -1)
        return ans;
    return query2(nod << 1|1, mid+1, dr, L, R);
}
int queryw(int nod, int st, int dr, int L, int R)
{
    if(L > R)
        return -1;
    if(dr < L || st > R)
        return -1;
    if(aint2[nod] <= val)
        return -1;
    if(st == dr)
        return st;
    int mid = (st + dr) / 2;
    int ans = queryw(nod << 1|1, mid+1, dr, L, R);
    if(ans != -1)
        return ans;
    return queryw(nod << 1, st, mid, L, R);
}
int queryw2(int nod, int st, int dr, int L, int R)
{
    if(L > R)
        return -1;
    if(dr < L || st > R)
        return -1;
    if(aint2[nod] <= val)
        return -1;
    if(st == dr)
        return st;
    int mid = (st + dr) / 2;
    int ans = queryw2(nod << 1, st, mid, L, R);
    if(ans != -1)
        return ans;
    return queryw2(nod << 1|1, mid+1, dr, L, R);
}
map<pair<pair<int, int>, int>, int>bst;
int solve(int L, int C)
{
    bst.clear();
    deque<pair<pair<int, int>, pair<int, int> > >d;
    d.pb({{L, C}, {0, 1}});
    d.pb({{L, C}, {0, 2}});
    int ia, ib, ic, id;
    int ans = 0;
    while(!d.empty())
    {
        pair<pair<int, int>, pair<int, int> > nod = d[0];
        d.pop_front();
        L = nod.fi.fi;
        C = nod.fi.se;
        ans = max(ans, nod.se.fi);
        if(nod.se.se == 1)
        {
            val = vh[L];
            ic = queryw2(1, 1, w, C+1, w);
            id = queryw(1, 1, w, 1, C-1);
            if(ic != -1)
            {
                if(bst.find({{L, ic}, 2}) != bst.end())
                {
                    if(nod.se.fi + ic - C <= bst[{{L, ic}, 2}])
                        continue;
                    bst[{{L, ic}, 2}] = nod.se.fi + ic - C;
                    d.pb({{L, ic}, {nod.se.fi + ic - C, 2}});
                }
                else
                {
                    bst[{{L, ic}, 2}] = nod.se.fi + ic - C;
                    d.pb({{L, ic}, {nod.se.fi + ic - C, 2}});
                }
            }
            else
                ans = max(ans, nod.se.fi + w - C);
            if(id != -1)
            {
                if(bst.find({{L, id}, 2}) != bst.end())
                {
                    if(nod.se.fi + C - id <= bst[{{L, ic}, 2}])
                        continue;
                    bst[{{L, id}, 2}] = nod.se.fi + C - id;
                    d.pb({{L, id}, {nod.se.fi + C - id, 2}});
                }
                else
                {
                    bst[{{L, id}, 2}] = nod.se.fi + C - id;
                    d.pb({{L, id}, {nod.se.fi + C - id, 2}});
                }
            }
            else
                ans = max(ans, nod.se.fi + C - 1);
        }
        else
        {
            val = vw[C];
            ia = query2(1, 1, h, L+1, h);
            ib = query(1, 1, h, 1, L-1);
            if(ia != -1)
            {
                if(bst.find({{ia, C}, 1}) != bst.end())
                {
                    if(nod.se.fi + ia - L <= bst[{{ia, C}, 1}])
                        continue;
                    bst[{{ia, C}, 2}] = nod.se.fi + ia - L;
                    d.pb({{ia, C}, {nod.se.fi + ia - L, 1}});
                }
                else
                {
                    bst[{{ia, C}, 2}] = nod.se.fi + ia - L;
                    d.pb({{ia, C}, {nod.se.fi + ia - L, 1}});
                }
            }
            else
                ans = max(ans, nod.se.fi + h - L);
            if(ib != -1)
            {
                if(bst.find({{ib, C}, 1}) != bst.end())
                {
                    if(nod.se.fi + L - ib <= bst[{{ib, C}, 1}])
                        continue;
                    bst[{{ib, C}, 2}] = nod.se.fi + L - ib;
                    d.pb({{ib, C}, {nod.se.fi + L - ib, 1}});
                }
                else
                {
                    bst[{{ib, C}, 2}] = nod.se.fi + L - ib;
                    d.pb({{ib, C}, {nod.se.fi + L - ib, 1}});
                }
            }
            else
                ans = max(ans, nod.se.fi + L - 1);
        }
    }
    return ans;
}
int main()
{
    cin >> h >> w >> q;
    for(int i = 1; i <= h; ++i)
        cin >> vh[i];
    for(int i = 1; i <= w; ++i)
        cin >> vw[i];
    build(1, 1, h);
    build2(1, 1, w);
    for(int i = 1; i <= q; ++i)
    {
        int L, C;
        cin >> L >> C;
        cout << solve(L, C) << '\n';
    }
    return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 504 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Incorrect 2011 ms 1244 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 504 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Incorrect 2011 ms 1244 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 380 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 504 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Incorrect 2011 ms 1244 KB Output isn't correct
20 Halted 0 ms 0 KB -