QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104344 | #6400. Game: Celeste | maomao90 | TL | 3ms | 7452kb | C++17 | 4.2kb | 2023-05-10 10:44:48 | 2023-05-10 10:44:51 |
Judging History
answer
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;
const int MAXL = 20;
const int MOD1 = 998244353;
const int MOD2 = 1000000007;
const int X = 1000003;
int t;
int n, l, r;
int x[MAXN], a[MAXN];
bool bad[MAXN];
ll pw1[MAXN], pw2[MAXN];
void init() {
pw1[0] = pw2[0] = 1;
REP (i, 1, n + 1) {
pw1[i] = pw1[i - 1] * X % MOD1;
pw2[i] = pw2[i - 1] * X % MOD2;
}
}
ii operator+(ii l, ii r) {
ii res = {l.FI + r.FI, l.SE + r.SE};
if (res.FI >= MOD1) {
res.FI -= MOD1;
}
if (res.SE >= MOD2) {
res.SE -= MOD2;
}
return res;
}
const int STSZ = MAXN * MAXL;
int st[STSZ], lc[STSZ], rc[STSZ], ptr;
ii hsh[STSZ];
void copy(int u, int v) {
st[u] = st[v];
lc[u] = lc[v];
rc[u] = rc[v];
hsh[u] = hsh[v];
}
void incre(int p, int x, int u, int v, int lo = 1, int hi = n) {
copy(u, v);
if (lo == hi) {
st[u] += x;
hsh[u] = hsh[u] + ii{pw1[lo] * x % MOD1, pw2[lo] * x % MOD2};
return;
}
int mid = lo + hi >> 1;
if (p <= mid) {
lc[u] = ptr++;
incre(p, x, lc[u], lc[v], lo, mid);
} else {
rc[u] = ptr++;
incre(p, x, rc[u], rc[v], mid + 1, hi);
}
st[u] = st[lc[u]] + st[rc[u]];
hsh[u] = hsh[lc[u]] + hsh[rc[u]];
}
// returns u - v of msb
int cmp(int u, int v, int lo = 1, int hi = n) {
if (hsh[u] == hsh[v]) {
return 0;
}
if (lo == hi) {
return st[u] - st[v];
}
int mid = lo + hi >> 1;
if (hsh[rc[u]] == hsh[rc[v]]) {
assert(hsh[lc[u]] != hsh[lc[v]]);
return cmp(lc[u], lc[v], lo, mid);
} else {
return cmp(rc[u], rc[v], mid + 1, hi);
}
}
vi ans;
void dfs(int u, int lo = 1, int hi = n) {
if (lo == hi) {
REP (z, 0, st[u]) {
ans.pb(lo);
}
return;
}
int mid = lo + hi >> 1;
dfs(rc[u], mid + 1, hi);
dfs(lc[u], lo, mid);
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> t;
while (t--) {
cin >> n >> l >> r;
REP (i, 1, n + 1) {
cin >> x[i];
}
REP (i, 1, n + 1) {
cin >> a[i];
}
init();
REP (i, 1, n + 1) {
bad[i] = 0;
}
ptr = n + 1;
incre(a[1], 1, 1, 1);
int iptr = 1;
deque<int> dq;
auto insert = [&] (int i) {
if (bad[i]) {
return;
}
while (!dq.empty() && cmp(i, dq.back()) >= 0) {
dq.pop_back();
}
dq.pb(i);
};
REP (i, 2, n + 1) {
while (iptr < i && x[iptr] + l <= x[i]) {
insert(iptr++);
}
while (!dq.empty() && x[dq.front()] + r < x[i]) {
dq.pop_front();
}
if (!dq.empty()) {
incre(a[i], 1, i, dq.front());
} else {
bad[i] = 1;
}
}
if (bad[n]) {
cout << -1 << '\n';
} else {
cout << st[n] << '\n';
dfs(n);
for (int i : ans) {
cout << i << ' ';
}
cout << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7452kb
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
Time Limit Exceeded
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 18 20 20 19 14 12 11 3 6 5 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 618 20 20 19 14 12 11 3 6 5 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 3...