oj.uz

Submission #195447

# Submission time Handle Problem Language Result Execution time Memory
195447 2020-01-16T07:58:22 Z stefdasca Abduction 2 (JOI17_abduction2) C++14
13 / 100
 5000 ms 385156 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();
        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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 2 ms 368 KB Output is correct
7 Correct 2 ms 236 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 2 ms 368 KB Output is correct
7 Correct 2 ms 236 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 416 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 5 ms 404 KB Output is correct
15 Correct 4 ms 380 KB Output is correct
16 Correct 0 ms 248 KB Output is correct
17 Correct 5 ms 348 KB Output is correct
18 Correct 7 ms 416 KB Output is correct
19 Execution timed out 5038 ms 384000 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 2 ms 368 KB Output is correct
7 Correct 2 ms 236 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 416 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 5 ms 404 KB Output is correct
15 Correct 4 ms 380 KB Output is correct
16 Correct 0 ms 248 KB Output is correct
17 Correct 5 ms 348 KB Output is correct
18 Correct 7 ms 416 KB Output is correct
19 Execution timed out 5038 ms 384000 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 604 KB Output is correct
2 Correct 21 ms 492 KB Output is correct
3 Correct 28 ms 480 KB Output is correct
4 Correct 30 ms 504 KB Output is correct
5 Correct 32 ms 604 KB Output is correct
6 Correct 45 ms 348 KB Output is correct
7 Correct 42 ms 380 KB Output is correct
8 Execution timed out 5090 ms 385156 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 2 ms 368 KB Output is correct
7 Correct 2 ms 236 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 5 ms 416 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 5 ms 404 KB Output is correct
15 Correct 4 ms 380 KB Output is correct
16 Correct 0 ms 248 KB Output is correct
17 Correct 5 ms 348 KB Output is correct
18 Correct 7 ms 416 KB Output is correct
19 Execution timed out 5038 ms 384000 KB Time limit exceeded
20 Halted 0 ms 0 KB -