QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412179#6400. Game: CelesteevirirWA 281ms4080kbC++206.2kb2024-05-16 10:05:062024-05-16 10:05:07

Judging History

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

  • [2024-05-16 10:05:07]
  • 评测
  • 测评结果:WA
  • 用时:281ms
  • 内存:4080kb
  • [2024-05-16 10:05:06]
  • 提交

answer

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
struct Hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;

ll add(ll a, ll b, ll m = MOD)
{
    a+=b;
    if(abs(a)>=m) a%=m;
    if(a<0) a+=m;
    return a;
}

ii operator+(const ii& a, const ii& b) { return {a.F + b.F, a.S + b.S}; }
ii& operator+=(ii& a, const ii& b) {
    a = a + b;
    return a;
}

struct Node
{
    ii val{0, 0};  // (val, cnt)
    int l = 0, r = 0;
};

vector<ll> dis;
vector<int> ans;

class PersistSegmentTree
{
private:
    int update(int pos, ii val, int k, int l, int r) {
        int k1 = createNode();
        v[k1] = v[k];
        if (l == r) {
            v[k1].val += val;
            return k1;
        }
        int mid = (l + r) >> 1;
        int cl = v[k1].l;
        int cr = v[k1].r;
        if (pos <= mid) {
            v[k1].l = update(pos, val, cl, l, mid);
            cl = v[k1].l;
        } else {
            v[k1].r = update(pos, val, cr, mid + 1, r);
            cr = v[k1].r;
        }
        v[k1].val = v[cl].val + v[cr].val;
        return k1;
    }
    bool le(int k1, int k2, int l, int r) {
        if (l == r) return v[k1].val.S <= v[k2].val.S;
        if (v[k1].val == v[k2].val) return true;
        int mid = (l + r) >> 1;
        int cr1 = v[k1].r;
        int cr2 = v[k2].r;
        if (v[cr1].val != v[cr2].val) return le(v[k1].r, v[k2].r, mid + 1, r);
        return le(v[k1].l, v[k2].l, l, mid);
    }
    void dfs(int k, int l, int r) {
        assert(k >= 0);
        if (v[k].val.S == 0) return;
        assert(k >= 1);
        if (l == r) {
            forn(i, 0, v[k].val.S) ans.pb(dis[l]);
            return;
        }
        int mid = (l + r) >> 1;
        dfs(v[k].r, mid + 1, r);
        dfs(v[k].l, l, mid);
    }
    // Node query(int s, int e, int k, int l, int r) {
    // 	if (r < l) return kInvalid;
    // 	if (s <= l && r <= e) return v[k].val;
    // 	int mid = (l + r) >> 1;
    // 	Node cl = query(s, e, k * 2, l, mid);
    // 	Node cr = query(s, e, k * 2 + 1, mid + 1, r);
    // 	return merge(cl, cr);
    // }

public:
    static constexpr ii kDefault = {0, 0};
    static constexpr ii kInvalid = {0, 0};
    int siz;
    vector<Node> v;
    PersistSegmentTree(int n) : siz(1), v(2, {kInvalid, 0, 0}) {
        while (siz < n) siz <<= 1;
    }
    int createNode() {
        v.push_back({{0, 0}, 0, 0});
        return sz(v) - 1;
    }
    int update(int pos, ii val, int k) {
        return update(pos, val, k, 0, siz - 1);
    }
    bool le(int k1, int k2) {
        return le(k1, k2, 0, siz - 1);
    }
    void dfs(int k) {
        return dfs(k, 0, siz - 1);
    }
    // ii query(int l, int r, int node) {
    // 	return query(l, r, node, 0, siz - 1);
    // }
};

mt19937 rng(727);

vector<ll> randVal(int n)
{
    unordered_set<ll> s;
    uniform_int_distribution<ll> dis(0, MOD - 1);
    forn(i,0,n)
    {
        int x = dis(rng);
        while (s.count(x)) x = dis(rng);
        s.insert(x);
    }
    return vector<ll>(all(s));
}

int compress(vector<ll>& v)
{
    set<ll> s(all(v));
    dis = vector<ll>(all(s));
    unordered_map<ll, ll, Hash> mp;
    forn(i,0,sz(dis)) mp[dis[i]] = i;
    forn(i,0,sz(v)) v[i] = mp[v[i]];
    return sz(dis);
}

void solve()
{
    int n; cin>>n;
    ll L, R; cin >> L >> R;
    vector<ll> x(n), a(n);
    forn(i,0,n) cin >> x[i];
    forn(i,0,n) cin >> a[i];
    vector<ll> a0(a);
    int m = compress(a);

    vector<ll> val = randVal(n);
    int l = 0, r = 0;
    PersistSegmentTree st(m);
    vector<int> roots;
    roots.reserve(n);
    deque<ii> dq;
    int rt0 = st.update(a[0], {val[0], 1}, 1);
    roots.pb(rt0);
    forn(i,1,n)
    {
        while (r < n && x[r] <= x[i] - L)
        {
            if (roots[r] != -1)
            {
                while (!dq.empty() && st.le(dq.back().F, roots[r])) dq.pop_back();
                dq.push_back({roots[r], r});
            }
            r++;
        }
        while (!dq.empty() && x[dq.front().S] < x[i] - R)
            dq.pop_front();
        int prt = -1;
        if (!dq.empty()) prt = dq.front().F;
        int k = prt == -1 ? -1 : st.update(a[i], {val[i], 1}, prt);
        roots.pb(k);
    }

    if (roots.back() != -1) st.dfs(roots.back());
    if (ans.empty())
    {
        cout << -1 << '\n';
        return;
    }
    cout << sz(ans) << '\n';
    for (const auto x : ans) cout<<x<<" ";
    cout << '\n';
    ans.clear();
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int t; cin>>t;
    fore(i,1,t) solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3656kb

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: 281ms
memory: 4080kb

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 ...

result:

wrong answer 10th lines differ - expected: '20 20 20 20 19 19 19 19 18 18 17 17 16 16 13 6 6 3', found: '20 20 20 20 19 19 19 19 18 18 17 16 16 13 12 6 6 3 '