Submission #403307

#	Time	Username	Problem	Language	Result	Execution time	Memory
403307		mjhmjh1104	Abduction 2 (JOI17_abduction2)	C++14	44 / 100	5043 ms	10056 KiB

abduction2

#include <map>
#include <tuple>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int tree_a[131072], tree_b[131072];
vector<tuple<int, int, int>> tv;

void interval_front(int i, int b, int e, int l, int r) {
    if (r < b || e < l) return;
    if (l <= b && e <= r) {
        tv.push_back({ i, b, e });
        return;
    }
    int m = (b + e) / 2;
    interval_front(i * 2 + 1, b, m, l, r);
    interval_front(i * 2 + 2, m + 1, e, l, r);
}

void interval_back(int i, int b, int e, int l, int r) {
    if (r < b || e < l) return;
    if (l <= b && e <= r) {
        tv.push_back({ i, b, e });
        return;
    }
    int m = (b + e) / 2;
    interval_back(i * 2 + 2, m + 1, e, l, r);
    interval_back(i * 2 + 1, b, m, l, r);
}

int lower_bound_left_real_a(int i, int b, int e, int v) {
    if (b == e) return b;
    int m = (b + e) / 2;
    if (tree_a[i * 2 + 2] > v) return lower_bound_left_real_a(i * 2 + 2, m + 1, e, v);
    return lower_bound_left_real_a(i * 2 + 1, b, m, v);
}

int lower_bound_left_real_b(int i, int b, int e, int v) {
    if (b == e) return b;
    int m = (b + e) / 2;
    if (tree_b[i * 2 + 2] > v) return lower_bound_left_real_b(i * 2 + 2, m + 1, e, v);
    return lower_bound_left_real_b(i * 2 + 1, b, m, v);
}

int lower_bound_right_real_a(int i, int b, int e, int v) {
    if (b == e) return b;
    int m = (b + e) / 2;
    if (tree_a[i * 2 + 1] > v) return lower_bound_right_real_a(i * 2 + 1, b, m, v);
    return lower_bound_right_real_a(i * 2 + 2, m + 1, e, v);
}

int lower_bound_right_real_b(int i, int b, int e, int v) {
    if (b == e) return b;
    int m = (b + e) / 2;
    if (tree_b[i * 2 + 1] > v) return lower_bound_right_real_b(i * 2 + 1, b, m, v);
    return lower_bound_right_real_b(i * 2 + 2, m + 1, e, v);
}

int lower_bound_left_a(int x, int v) {
    tv.clear();
    interval_back(0, 0, 65535, 0, x);
    for (auto &i: tv) {
        auto [ a, b, c ] = i;
        if (tree_a[a] > v) return lower_bound_left_real_a(a, b, c, v);
    }
    return -1;
}

int lower_bound_left_b(int x, int v) {
    tv.clear();
    interval_back(0, 0, 65535, 0, x);
    for (auto &i: tv) {
        auto [ a, b, c ] = i;
        if (tree_b[a] > v) return lower_bound_left_real_b(a, b, c, v);
    }
    return -1;
}

int lower_bound_right_a(int x, int v) {
    tv.clear();
    interval_front(0, 0, 65535, x, 65535);
    for (auto &i: tv) {
        auto [ a, b, c ] = i;
        if (tree_a[a] > v) return lower_bound_right_real_a(a, b, c, v);
    }
    return 65536;
}

int lower_bound_right_b(int x, int v) {
    tv.clear();
    interval_front(0, 0, 65535, x, 65535);
    for (auto &i: tv) {
        auto [ a, b, c ] = i;
        if (tree_b[a] > v) return lower_bound_right_real_b(a, b, c, v);
    }
    return 65536;
}

int h, w, q;
int a[50006], b[50006], rt[100006];
pair<int, bool> lt[100006];
vector<pair<int, long long>> v[100006];
vector<int> compress;

int main() {
    scanf("%d%d%d", &w, &h, &q);
    for (int i = 0; i < w; i++) scanf("%d", a + i);
    for (int i = 0; i < h; i++) scanf("%d", b + i);
    for (int i = 0; i < w; i++) compress.push_back(a[i]);
    for (int i = 0; i < h; i++) compress.push_back(b[i]);
    sort(compress.begin(), compress.end());
    for (int i = 0; i < w; i++) a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin();
    for (int i = 0; i < h; i++) b[i] = lower_bound(compress.begin(), compress.end(), b[i]) - compress.begin();
    for (int i = 0; i < w; i++) lt[a[i]] = { i, false };
    for (int i = 0; i < h; i++) lt[b[i]] = { i, true };
    for (int i = 0; i < w; i++) tree_a[65535 + i] = a[i];
    for (int i = 0; i < h; i++) tree_b[65535 + i] = b[i];
    for (int i = 65534; i >= 0; i--) {
        tree_a[i] = max(tree_a[i * 2 + 1], tree_a[i * 2 + 2]);
        tree_b[i] = max(tree_b[i * 2 + 1], tree_b[i * 2 + 2]);
    }
    for (int i = 0; i < q; i++) {
        int s, t;
        scanf("%d%d", &t, &s);
        s--, t--;
        long long res = 0;
        if (s > 0) { // up
            for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
            int it = lower_bound_left_b(s - 1, a[t]);
            if (it < 0) res = max(res, (long long)s);
            else {
                v[b[it]].push_back({ t, s - it });
                rt[b[it]] = lower_bound_left_a(t, b[it]);
                for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
                    if (!lt[i].second) {
                        int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
                        if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[above]);
                            if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
                            v[b[above]].push_back({ lt[i].first, ret });
                            rt[b[above]] = tmp;
                        }
                        if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
                            if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
                            v[b[bottom]].push_back({ lt[i].first, ret });
                            rt[b[bottom]] = tmp;
                        }
                    } else {
                        int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
                        if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[left]);
                            if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
                            v[a[left]].push_back({ lt[i].first, ret });
                            rt[a[left]] = tmp;
                        }
                        if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[right]);
                            if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
                            v[a[right]].push_back({ lt[i].first, ret });
                            rt[a[right]] = tmp;
                        }
                    }
                }
            }
        }
        if (s < h - 1) { // down
            for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
            int it = lower_bound_right_b(s + 1, a[t]);
            if (it >= 65536) res = max(res, (long long)(h - 1 - s));
            else {
                v[b[it]].push_back({ t, it - s });
                rt[b[it]] = lower_bound_left_a(t, b[it]);
                for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
                    if (!lt[i].second) {
                        int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
                        if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[above]);
                            if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
                            v[b[above]].push_back({ lt[i].first, ret });
                            rt[b[above]] = tmp;
                        }
                        if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
                            if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
                            v[b[bottom]].push_back({ lt[i].first, ret });
                            rt[b[bottom]] = tmp;
                        }
                    } else {
                        int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
                        if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[left]);
                            if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
                            v[a[left]].push_back({ lt[i].first, ret });
                            rt[a[left]] = tmp;
                        }
                        if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[right]);
                            if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
                            v[a[right]].push_back({ lt[i].first, ret });
                            rt[a[right]] = tmp;
                        }
                    }
                }
            }
        }
        if (t > 0) { // left
            for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
            int it = lower_bound_left_a(t - 1, b[s]);
            if (it < 0) res = max(res, (long long)t);
            else {
                v[a[it]].push_back({ s, t - it });
                rt[a[it]] = lower_bound_left_b(s, a[it]);
                for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
                    if (!lt[i].second) {
                        int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
                        if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[above]);
                            if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
                            v[b[above]].push_back({ lt[i].first, ret });
                            rt[b[above]] = tmp;
                        }
                        if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
                            if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
                            v[b[bottom]].push_back({ lt[i].first, ret });
                            rt[b[bottom]] = tmp;
                        }
                    } else {
                        int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
                        if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[left]);
                            if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
                            v[a[left]].push_back({ lt[i].first, ret });
                            rt[a[left]] = tmp;
                        }
                        if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[right]);
                            if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
                            v[a[right]].push_back({ lt[i].first, ret });
                            rt[a[right]] = tmp;
                        }
                    }
                }
            }
        }
        if (t < w - 1) { // right
            for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
            int it = lower_bound_right_a(t + 1, b[s]);
            if (it >= 65536) res = max(res, (long long)(w - 1 - t));
            else {
                v[a[it]].push_back({ s, it - t });
                rt[a[it]] = lower_bound_left_b(s, a[it]);
                for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
                    if (!lt[i].second) {
                        int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
                        if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[above]);
                            if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
                            v[b[above]].push_back({ lt[i].first, ret });
                            rt[b[above]] = tmp;
                        }
                        if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
                            if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
                            v[b[bottom]].push_back({ lt[i].first, ret });
                            rt[b[bottom]] = tmp;
                        }
                    } else {
                        int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
                        if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[left]);
                            if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
                            v[a[left]].push_back({ lt[i].first, ret });
                            rt[a[left]] = tmp;
                        }
                        if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
                        else {
                            int tmp = lower_bound_left_b(lt[i].first, a[right]);
                            if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
                            long long ret = 0;
                            for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
                            v[a[right]].push_back({ lt[i].first, ret });
                            rt[a[right]] = tmp;
                        }
                    }
                }
            }
        }
        printf("%lld\n", res);
    }
}

Compilation message (stderr)

abduction2.cpp: In function 'int lower_bound_left_a(int, int)':
abduction2.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int lower_bound_left_b(int, int)':
abduction2.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int lower_bound_right_a(int, int)':
abduction2.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int lower_bound_right_b(int, int)':
abduction2.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d%d%d", &w, &h, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:109:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     for (int i = 0; i < w; i++) scanf("%d", a + i);
      |                                 ~~~~~^~~~~~~~~~~~~
abduction2.cpp:110:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     for (int i = 0; i < h; i++) scanf("%d", b + i);
      |                                 ~~~~~^~~~~~~~~~~~~
abduction2.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf("%d%d", &t, &s);
      |         ~~~~~^~~~~~~~~~~~~~~~

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