QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412179 | #6400. Game: Celeste | evirir | WA | 281ms | 4080kb | C++20 | 6.2kb | 2024-05-16 10:05:06 | 2024-05-16 10:05:07 |
Judging History
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 '