QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429896#8780. Training, Round 2skittles1412#Compile Error//C++178.0kb2024-06-03 01:28:172024-06-03 01:28:17

Judging History

你现在查看的是最新测评结果

  • [2024-06-03 01:28:17]
  • 评测
  • [2024-06-03 01:28:17]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif

#line 1 "m.cpp"
// 69683a8183e36171b0123a3fbef815656276c8d9
#include "bits/extc++.h"
#line 1 "/home/skittles1412/workspace/cp/library/template.hpp"



#line 5 "/home/skittles1412/workspace/cp/library/template.hpp"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

using u32 = uint32_t;
using u64 = uint64_t;
using ld = long double;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))


#line 1 "/home/skittles1412/workspace/cp/library/utils.hpp"



#line 5 "/home/skittles1412/workspace/cp/library/utils.hpp"

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T, size_t N>
ostream& operator<<(ostream& out, const array<T, N>& arr) {
    out << "[";
    for (size_t i = 0; i < N; i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

/**
 * Computes the first x in [l, r) such that cb(x) is true.
 *
 * If no x in that range is true, returns r
 */
template <typename T, typename Cb>
T first_true(T l, T r, const Cb& cb) {
    while (l < r) {
        T mid = (l + r) / 2;
        if (cb(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

/**
 * Computes the last x in (l, r] such that cb(x) is true.
 *
 * If no x in that range is true, returns l
 */
template <typename T, typename Cb>
T last_true(T l, T r, const Cb& cb) {
    while (l < r) {
        T mid = (l + r + 1) / 2;
        if (cb(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

template <typename T>
bool is_palin(const T& arr) {
    return arr == reversed(arr);
}

template <typename T>
T sorted(T arr) {
    sort(begin(arr), end(arr));
    return arr;
}

template <typename T>
T negated(T arr) {
    for (auto& a : arr) {
        a = -a;
    }
    return arr;
}

template <typename T, bool STRICT>
vector<int> comp_prev_helper(const vector<T>& arr) {
    int n = sz(arr);

    vector<int> ans(n);

    vector<pair<int, int>> st;
    for (int i = 0; i < n; i++) {
        auto cmp = [&]() -> bool {
            if constexpr (STRICT) {
                return st.back().first <= arr[i];
            } else {
                return st.back().first < arr[i];
            }
        };
        while (sz(st) && cmp()) {
            st.pop_back();
        }

        if (sz(st)) {
            ans[i] = st.back().second;
        } else {
            ans[i] = -1;
        }
        st.emplace_back(arr[i], i);
    }

    return ans;
}

/**
 * Computes ans[i], the closest index j to the left of i where arr[j] > arr[i]
 *
 * ans[i] = -1 if no such j exists
 */
template <typename T>
vector<int> comp_prev_gt(const vector<T>& arr) {
    return comp_prev_helper<T, true>(arr);
}

/**
 * Computes ans[i], the closest index j to the left of i where arr[j] >= arr[i]
 *
 * ans[i] = -1 if no such j exists
 */
template <typename T>
vector<int> comp_prev_ge(const vector<T>& arr) {
    return comp_prev_helper<T, false>(arr);
}

/**
 * reverses an array of indices
 *
 * specifically, it reverses the array and computes arr[i] = n - 1 - arr[i]
 */
vector<int> reverse_indices(vector<int> arr) {
    int n = sz(arr);

    reverse(begin(arr), end(arr));
    for (auto& a : arr) {
        a = n - 1 - a;
    }

    return arr;
}

/**
 * Computes ans[i], the closest index j to the right of i where arr[j] > arr[i]
 *
 * ans[i] = n if no such j exists
 */
template <typename T>
vector<int> comp_next_gt(vector<T> arr) {
    reverse(begin(arr), end(arr));

    return reverse_indices(comp_prev_gt(arr));
}

/**
 * Computes ans[i], the closest index j to the right of i where arr[j] >= arr[i]
 *
 * ans[i] = n if no such j exists
 */
template <typename T>
vector<int> comp_next_ge(vector<T> arr) {
    reverse(begin(arr), end(arr));

    return reverse_indices(comp_prev_ge(arr));
}

template <typename Cb>
struct CmpByKey {
    Cb cb;

    explicit CmpByKey(const Cb& cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

/**
 * outputs will be in the range [0, m), returns m
 */
int coord_comp(const vector<int*>& arr) {
    vector<int> vals;
    for (auto& a : arr) {
        vals.push_back(*a);
    }

    sort(begin(vals), end(vals));
    vals.erase(unique(begin(vals), end(vals)), end(vals));

    for (auto& a : arr) {
        *a = int(lower_bound(begin(vals), end(vals), *a) - begin(vals));
    }

    return sz(vals);
}

/**
 * outputs will be in the range [0, m), returns {m, result}
 */
template <typename T>
pair<int, vector<int>> coord_comp(const vector<T>& arr) {
    vector<T> vals = arr;
    sort(begin(vals), end(vals));
    vals.erase(unique(begin(vals), end(vals)), end(vals));

    vector<int> ans;
    for (auto& a : arr) {
        ans.push_back(
            int(lower_bound(begin(vals), end(vals), a) - begin(vals)));
    }

    return {sz(vals), ans};
}

template <typename T>
bool on(T mask, int bit) {
    return (mask >> bit) & 1;
}


#line 5 "m.cpp"

constexpr int MAXN = 5e3 + 200, MAXB = (MAXN >> 6) + 1;

u64 pref_mask(int x) {
    return (u64(1) << x) - 1;
}

u64 pref_mask2(int x) {
    if (x == 64) {
        return ~u64(0);
    }
    return (u64(1) << x) - 1;
}

void solve() {
    int n, ix, iy;
    cin >> n >> ix >> iy;

    int arr[n][4];
    for (auto& [xl, xr, yl, yr] : arr) {
        cin >> xl >> xr >> yl >> yr;
        xl -= ix;
        xr -= ix;
        yl -= ix;
        yr -= ix;
    }

    u64 dp[n + 1][MAXB] {};
    dp[0][0] |= 1;

    for (auto& [xl, xr, yl, yr] : arr) {
        xl = max(xl, 0);
        xr = min(xr, n - 1);
        yl = max(yl, 0);
        yr = min(yr, n - 1);
        if (xl > xr || yl > yr) {
            continue;
        }
        yr++;

        for (int x = xr; x >= xl; x--) {
            u64 cval[MAXB];

            memcpy(cval, dp[x], sizeof(cval));

            fill(cval, cval + (yl >> 6), 0);
            cval[yl >> 6] &= ~pref_mask(yl & 63);
            fill(cval + (yr >> 6) + 1, end(cval), 0);
            cval[yr >> 6] &= pref_mask(yr & 63);

            for (int i = 0; i < MAXB; i++) {
                dp[x + 1][i] |= cval[i];
            }

            for (int i = 0; i < MAXB; i++) {
                dp[x][i] |= cval[i] << 1;
            }
            for (int i = 1; i < MAXB; i++) {
                dp[x][i] |= on(cval[i - 1], 63);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (on(dp[i][j >> 6], j & 63)) {
                ans = max(ans, i + j);
            }
        }
    }

    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}

详细

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/extc++.h:32,
                 from m.cpp:2:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~