제출 #558385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558385		fatemetmhr	유괴 2 (JOI17_abduction2)	C++17	100 / 100	1689 ms	10024 KiB

abduction2

// Be name khoda //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define pb          push_back


const int maxn5 = 1e5 + 10;
const int maxnt = 4e5 + 10;

struct segment_tree{

    int val[maxn5];
    int mx[maxnt];

    inline void build(int l, int r, int v){
        if(r - l == 1){
            mx[v] = val[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    }

    inline int get_first(int l, int r, int lq, int rq, int val, int v){
        if(rq <= l || r <= lq || mx[v] <= val)
            return -1;
        if(r - l == 1)
            return l;
        int mid = (l + r) >> 1;
        int ans = get_first(l, mid, lq, rq, val, v * 2);
        if(ans != -1)
            return ans;
        return get_first(mid, r, lq, rq, val, v * 2 + 1);
    }

    inline int get_last(int l, int r, int lq, int rq, int val, int v){
        if(rq <= l || r <= lq || mx[v] <= val)
            return -1;
        if(r - l == 1)
            return l;
        int mid = (l + r) >> 1;
        int ans = get_last(mid, r, lq, rq, val, v * 2 + 1);
        if(ans != -1)
            return ans;
        return get_last(l, mid, lq, rq, val, v * 2);
    }

} seg1, seg2;

int a[maxn5], b[maxn5], pt1[2][maxn5], pt2[2][maxn5];
int up[maxn5], dw[maxn5], lef[maxn5], rig[maxn5];
vector <pair<pair<int, int>, bool>> av;
ll ans[2][2][maxn5], n, m, x, y;

inline ll setmn(ll a, ll b){
    if(a == -1)
        return b;
    if(b == -1)
        return a;
    return min(a, b);
}

inline ll setmx(ll a, ll b){
    if(a == -1)
        return b;
    if(b == -1)
        return a;
    return max(a, b);
}

inline ll solve(bool exty){
    //cout << "satring with solve " << endl;  
    for(auto [p, ty] : av){
        int id = p.se;
        if(ty && up[id] == -1)
            continue;
        if(!ty && lef[id] == -1)
            continue;
        if(ty){ // stoon
            int pt = seg1.get_last(0, n, 0, up[id] + 1, b[id], 1);
            if(pt != -1){
                lef[pt] = setmn(lef[pt], id);
                rig[pt] = setmx(rig[pt], id);
            }
            else{
                ans[ty][0][id] = up[id];
            }
            pt1[ty][id] = pt;
            pt = seg1.get_first(0, n, dw[id], n, b[id], 1);
            if(pt != -1){
                lef[pt] = setmn(lef[pt], id);
                rig[pt] = setmx(rig[pt], id);
            }
            else{
                ans[ty][1][id] = n - dw[id] - 1;
            }
            pt2[ty][id] = pt;
        }
        else{ // satr
            int pt = seg2.get_last(0, m, 0, lef[id] + 1, a[id], 1);
            if(pt != -1){
                dw[pt] = setmx(dw[pt], id);
                up[pt] = setmn(up[pt], id);
            }
            else{
                ans[ty][0][id] = lef[id];
            }
            pt1[ty][id] = pt;
            pt = seg2.get_first(0, m, rig[id], m, a[id], 1);
            if(pt != -1){
                dw[pt] = setmx(dw[pt], id);
                up[pt] = setmn(up[pt], id);
            }
            else{
                ans[ty][1][id] = m - rig[id] - 1;
            }
            pt2[ty][id] = pt;
        }
        //cout << ty << ' ' << id << ' ' << lef[id] << ' ' << rig[id] << ' ' << up[id] << ' ' << dw[id] << endl;
        //cout << "edame " << pt1[ty][id] << ' ' << pt2[ty][id] << ' ' << ans[ty][0][id] << ' ' << ans[ty][1][id] << endl;
    }

    reverse(all(av));

    for(auto [p, ty] : av){
        int id = p.se;
        if(ty && up[id] == -1)
            continue;
        if(!ty && lef[id] == -1)
            continue;
        int pt = pt1[ty][id];
        if(pt1[ty][id] != -1){
            if(ty){
                ans[ty][0][id] = max(ans[ty ^ 1][0][pt] + id - lef[pt], ans[ty ^ 1][1][pt] + rig[pt] - id) + up[id] - pt;
            }
            else{
                ans[ty][0][id] = max(ans[ty ^ 1][0][pt] + id - up[pt], ans[ty ^ 1][1][pt] + dw[pt] - id) + lef[id] - pt;
            }
        }
        pt = pt2[ty][id];
        if(pt != -1){
            if(ty){
                ans[ty][1][id] = max(ans[ty ^ 1][0][pt] + id - lef[pt], ans[ty ^ 1][1][pt] + rig[pt] - id) + pt - dw[id];
            }
            else{
                ans[ty][1][id] = max(ans[ty ^ 1][0][pt] + id - up[pt], ans[ty ^ 1][1][pt] + dw[pt] - id) + pt - rig[id];
            }
        }
        //cout << "ans of " << ty << ' '<< id << ' ' << ans[ty][0][id] << ' ' << ans[ty][1][id] << endl;
    }

    //cout << max({ans[0][0][x], ans[0][1][x], ans[1][0][y], ans[1][1][y]}) << '\n';

    reverse(all(av));
    if(exty){
        ans[1][0][y] = ans[1][1][y] = (up[y] < x ? ans[1][0][y] : ans[1][1][y]);
        return max({ans[0][0][x], ans[0][1][x], ans[1][0][y] + 1, ans[1][1][y] + 1});
    }
    else{
        ans[0][0][x] = ans[0][1][x] = (lef[x] > y ? ans[0][1][x] : ans[0][0][x]);
        return max({ans[0][0][x] + 1, ans[0][1][x] + 1, ans[1][0][y], ans[1][1][y]});
    }
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int q; cin >> n >> m >> q;

    for(int i = 0; i < n; i++){
        cin >> a[i];
        seg1.val[i] = a[i];
        av.pb({{a[i], i}, 0});
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
        seg2.val[i] = b[i];
        av.pb({{b[i], i}, 1});
    }

    sort(all(av));

    seg1.build(0, n, 1);
    seg2.build(0, m, 1);

    for(int i = 0; i < q; i++){
        cin >> x >> y;
        x--; y--;

        ll anss = 0;
        if(a[x] > b[y]){
            memset(lef, -1, sizeof lef);
            memset(rig, -1, sizeof rig);
            memset(up, -1, sizeof up);
            memset(dw, -1, sizeof dw);
            memset(ans, 0, sizeof ans);

            lef[x] = rig[x] = y;
            up[y] = dw[y] = x - 1;
            if(x > 0)
                anss = max(anss, solve(true));

            memset(lef, -1, sizeof lef);
            memset(rig, -1, sizeof rig);
            memset(up, -1, sizeof up);
            memset(dw, -1, sizeof dw);
            memset(ans, 0, sizeof ans);

            lef[x] = rig[x] = y;
            up[y] = dw[y] = x + 1;
            if(x + 1 < n)
                anss = max(anss, solve(true));

        }
        else{
            memset(lef, -1, sizeof lef);
            memset(rig, -1, sizeof rig);
            memset(up, -1, sizeof up);
            memset(dw, -1, sizeof dw);
            memset(ans, 0, sizeof ans);

            up[y] = dw[y] = x;
            lef[x] = rig[x] = y - 1;
            if(y > 0)
                anss = max(anss, solve(false));

            memset(lef, -1, sizeof lef);
            memset(rig, -1, sizeof rig);
            memset(up, -1, sizeof up);
            memset(dw, -1, sizeof dw);
            memset(ans, 0, sizeof ans);

            up[y] = dw[y] = x;
            lef[x] = rig[x] = y + 1;
            if(y + 1 < m)
                anss = max(anss, solve(false));
        }

        cout << anss << '\n';

    }
}

/*
3 3 1
3 2 6
1 4 5
3 3
*/

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56