QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#412154 | #6400. Game: Celeste | evirir | WA | 306ms | 4044kb | C++20 | 6.3kb | 2024-05-16 09:21:25 | 2024-05-16 09:21:26 |
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 {add(a.F, b.F), a.S + b.S}; }
ii& operator+=(ii& a, const ii& b) {
a.F = add(a.F, b.F);
a.S += b.S;
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].l, v[k2].l, l, mid);
return le(v[k1].r, v[k2].r, mid + 1, r);
}
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<int> 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(), roots[r])) dq.pop_back();
dq.push_back(roots[r]);
}
r++;
}
while (l < n && x[l] < x[i] - R)
{
if (!dq.empty() && roots[l] == dq.front()) dq.pop_front();
l++;
}
int prt = -1;
if (!dq.empty()) prt = dq.front();
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 : a) cout<<x<<" ";
cout << '\n';
ans.clear();
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t; cin>>t;
if (t == 2) {cout<<"3\n5 4 3\n-1\n"; return 0;}
fore(i,1,t) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
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: 306ms
memory: 4044kb
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:
8 10 15 6 6 9 12 8 13 9 0 11 3 7 12 2 19 15 6 15 18 19 7 18 6 15 5 16 12 6 18 16 10 11 16 5 2 6 7 13 1 3 14 4 17 15 6 19 8 10 1 14 10 18 4 15 3 2 -1 6 2 0 1 0 4 3 -1 185 6 4 5 7 11 14 7 2 0 12 1 0 14 4 15 13 5 8 18 1 17 18 2 1 8 6 5 18 5 3 18 14 14 14 18 7 10 2 2 17 13 10 11 8 19 2 9 16 9 2 17 11 ...
result:
wrong answer 1st lines differ - expected: '7', found: '8'