QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103737#6400. Game: CelestehitonanodeWA 349ms3804kbC++1714.3kb2023-05-07 14:00:502023-05-07 14:00:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 14:00:55]
  • 评测
  • 测评结果：WA
  • 用时：349ms
  • 内存：3804kb
查看
  • [2023-05-07 14:00:50]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T, typename V>
void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }
template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }
template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr)
#else
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif


// Sliding-Window Aggregation based queue
// - `std::queue`-like data structure with monoid operation
// - Each operation is amortized O(1)
// - Verification:
// https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-lcm-interval/submissions/code/1317888077
// - Reference:
// https://github.com/NiMiLib/NoshiMochiLibrary/blob/queue_aggregation/lib/data_structure/sequence/queue_aggregation.hpp
template <typename T_VAL, typename T_PROD, T_PROD (*val2prod)(T_VAL), T_PROD (*op)(T_PROD, T_PROD)>
struct swag_queue {
    std::stack<std::pair<T_VAL, T_PROD>, std::vector<std::pair<T_VAL, T_PROD>>> front_stack,
        back_stack;

    swag_queue() {}
    bool empty() const { return front_stack.empty() and back_stack.empty(); }
    int size() const { return front_stack.size() + back_stack.size(); }
    T_PROD fold_all() const {
        if (empty()) {
            exit(1);
            // return ID_;
        } else if (front_stack.empty())
            return back_stack.top().second;
        else if (back_stack.empty())
            return front_stack.top().second;
        else
            return op(front_stack.top().second, back_stack.top().second);
    }
    void push(const T_VAL &x) {
        if (back_stack.empty())
            back_stack.emplace(x, val2prod(x));
        else
            back_stack.emplace(x, op(back_stack.top().second, val2prod(x)));
    }
    const T_VAL &front() {
        if (front_stack.empty()) {
            front_stack.emplace(back_stack.top().first, val2prod(back_stack.top().first));
            back_stack.pop();
            while (!back_stack.empty()) {
                T_VAL t = back_stack.top().first;
                front_stack.emplace(t, op(val2prod(t), front_stack.top().second));
                back_stack.pop();
            }
        }
        return front_stack.top().first;
    }

    T_VAL pop() {
        T_VAL t = front();
        front_stack.pop();
        return t;
    }
};


template <class S, S (*op)(S, S), S (*e)()> struct persistent_segtree {
    struct Root {
        int id;
    };

    explicit persistent_segtree(int n) : persistent_segtree(std::vector<S>(n, e())) {}
    explicit persistent_segtree(const std::vector<S> &v) : _n(int(v.size())) {
        lg = 1;
        while ((1 << lg) < _n) ++lg;
        size = 1 << lg;

        d = std::vector<S>(2 * size, e());
        left = right = std::vector<int>(2 * size, -1);

        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            left.at(i) = 2 * i;
            right.at(i) = 2 * i + 1;
            d.at(i) = op(d.at(2 * i), d.at(2 * i + 1));
        }
    }


    Root set(const Root &root, int p, const S &x) {
        assert(0 <= p && p < _n);

        static std::vector<int> ids;
        if (int(ids.size()) < lg + 1) ids.resize(lg + 1, -1);

        ids.at(lg) = root.id;
        for (int i = lg - 1; i >= 0; --i) {
            ids.at(i) = ((p >> i) & 1) ? right.at(ids.at(i + 1)) : left.at(ids.at(i + 1));
        }
        dbg(ids);

        int copy_cur = d.size();
        d.push_back(x);
        left.push_back(-1);
        right.push_back(-1);

        for (int i = 1; i <= lg; i++) {
            int par = ids.at(i), cur = ids.at(i - 1);
            const int copy_par = d.size();
            left.push_back(left.at(par) == cur ? copy_cur : left.at(par));
            right.push_back(right.at(par) == cur ? copy_cur : right.at(par));
            d.push_back(op(d.at(left.back()), d.at(right.back())));

            copy_cur = copy_par;
        }

        return Root{copy_cur};
    }

    S prod(const Root &root, int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);

        auto rec = [&](auto &&self, int i, int lo, int hi) -> S {
            if (r <= lo or hi <= l) return e();
            if (l <= lo and hi <= r) return d.at(i);

            return op(self(self, left.at(i), lo, (lo + hi) / 2), self(self, right.at(i), (lo + hi) / 2, hi));
        };

        return rec(rec, root.id, 0, size);
    }

    S all_prod(const Root &root) const { return d.at(root.id); }

    Root get_root() const { return {1}; }

// private:
    int _n, size, lg;
    std::vector<S> d;
    std::vector<int> left, right;
};

struct rand_int_ {
    using lint = long long;
    std::mt19937 mt;
    rand_int_() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    lint operator()(lint x) { return this->operator()(0, x); } // [0, x)
    lint operator()(lint l, lint r) {
        std::uniform_int_distribution<lint> d(l, r - 1);
        return d(mt);
    }
} rnd;



using S = pair<int, unsigned long long>;
S op(S l, S r) { return l + r; }
S e() { return {0, 0}; }
persistent_segtree<S, op, e> tree(0);

using swag_val = pair<int, persistent_segtree<S, op, e>::Root>;
swag_val val2prod(swag_val x) { return x; }
swag_val swag_op(swag_val l, swag_val r) {
    int i = l.second.id, j = r.second.id;

    if (tree.d.at(i) == tree.d.at(j)) return l;

    dbg(make_tuple(l.first, r.first));
    dbg(make_tuple(i, j, tree.d.at(i), tree.d.at(j)));

    for (int d = 0; d < tree.lg; ++d) {
        if (const int il = tree.left.at(i), jl = tree.left.at(j); tree.d.at(il) != tree.d.at(jl)) {
            i = il;
            j = jl;
        } else {
            i = tree.right.at(i);
            j = tree.right.at(j);
        }
    }

    dbg(make_tuple(i, j, tree.d.at(i), tree.d.at(j)));

    return tree.d.at(i) > tree.d.at(j) ? l : r;
}

vector<int> solve() {
    int N, L, R;
    cin >> N >> L >> R;
    vector<int> X(N);
    cin >> X;
    vector<int> A(N);
    cin >> A;
    REP(i, N) A.at(i) = N - A.at(i);
    dbg(make_tuple(L, R, X, A));


    tree = persistent_segtree<S, op, e>(N);
    vector<unsigned long long> hash(N);
    for (auto &x : hash) x = rnd(0, 1LL << 60);
    dbg(hash);

    auto root0 = tree.get_root();

    swag_queue<swag_val, swag_val, val2prod, swag_op> swag;

    queue<swag_val> roots;
    roots.emplace(0, tree.set(root0, A.at(0), {1, hash.at(A.at(0))}));

    vector<int> prv(N, -1);

    dbg(tree.d);

    FOR(i, 1, N) {
        while (roots.size() and X.at(roots.front().first) <= X.at(i) - L) {
            swag.push(roots.front());
            roots.pop();
        }
        while (swag.size() and X.at(swag.front().first) < X.at(i) - R) swag.pop();

        dbg(make_tuple(i, swag.size()));

        if (swag.size()) {
            auto [j, root] = swag.fold_all();
            prv.at(i) = j;
            auto f = tree.prod(root, A.at(i), A.at(i) + 1);
            f.first++;
            f.second += hash.at(A.at(i));
            auto new_root = tree.set(root, A.at(i), f);
            roots.emplace(i, new_root);
            dbg(make_tuple(root.id, new_root.id, tree.d.at(root.id), tree.d.at(new_root.id)));
            dbg(tree.all_prod(new_root));
        }
    }

    dbg(tree.left);
    dbg(tree.right);


    if (prv.back() < 0) return {};

    vector<int> ret;
    for (int cur = N - 1; cur >= 0; cur = prv.at(cur)) ret.push_back(N - A.at(cur));

    sort(ret.rbegin(), ret.rend());
    return ret;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        auto ret = solve();
        if (ret.empty()) {
            cout << "-1\n";
        } else {
            cout << ret.size() << '\n';
            REP(i, ret.size()) cout << ret.at(i) << (i + 1 == int(ret.size()) ? '\n' : ' ');
        }
    }
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3380kb

input:

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

output:

3
5 4 3
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 349ms
memory: 3804kb

input:

10000
57 8 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...

output:

7
20 20 19 14 12 11 3
-1
6
6 5 3 2 1 1
-1
185
20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 12...

result:

wrong answer 66th lines differ - expected: '1', found: '-1'
English 繁體中文 简体中文

伺服器時間: 2024-12-02 23:53:35 | 開源專案