Submission #195447

#	Time	Username	Problem	Language	Result	Execution time	Memory
195447		stefdasca	Abduction 2 (JOI17_abduction2)	C++14	13 / 100	5090 ms	385156 KiB

abduction2

#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();
        if(bst.find({{L, C}, nod.se.se}) != bst.end())
        {
            if(nod.se.fi <= bst[{{L, C}, nod.se.se}])
                continue;
            bst[{{L, C}, nod.se.se}] = nod.se.fi;
        }
        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)
                d.pb({{L, ic}, {nod.se.fi + ic - C, 2}});
            else
                ans = max(ans, nod.se.fi + w - C);
            if(id != -1)
                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)
                d.pb({{ia, C}, {nod.se.fi + ia - L, 1}});
            else
                ans = max(ans, nod.se.fi + h - L);
            if(ib != -1)
                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 / 13
• Subtask 2: 0 / 10
• Subtask 3: 0 / 17
• Subtask 4: 0 / 4
• Subtask 5: 0 / 56