QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #104385 | #6400. Game: Celeste | maomao90 | TL | 2ms | 25908kb | C++17 | 4.3kb | 2023-05-10 16:27:46 | 2023-05-10 16:27:50 |
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 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, MAXN) {
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 u, int v, int lo = 1, int hi = n) {
copy(u, v);
if (lo == hi) {
st[u]++;
//hsh[u] = hsh[u] + ii{pw1[lo] * x % MOD1, pw2[lo] * x % MOD2};
hsh[u] = hsh[u] + pw1[lo];
if (hsh[u] >= MOD1) {
hsh[u] -= MOD1;
}
return;
}
int mid = lo + hi >> 1;
if (p <= mid) {
lc[u] = ptr++;
incre(p, lc[u], lc[v], lo, mid);
} else {
rc[u] = ptr++;
incre(p, rc[u], rc[v], mid + 1, hi);
}
st[u] = st[lc[u]] + st[rc[u]];
hsh[u] = hsh[lc[u]] + hsh[rc[u]];
if (hsh[u] >= MOD1) {
hsh[u] -= MOD1;
}
}
// returns u - v of msb
int cmp(int u, int v, int lo = 1, int hi = n) {
while (1) {
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]]);
u = lc[u]; v = lc[v];
hi = mid;
} else {
u = rc[u]; v = rc[v];
lo = mid + 1;
}
}
}
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
init();
cin >> t;
while (t--) {
cin >> n >> l >> r;
REP (i, 1, n + 1) {
cin >> x[i];
}
REP (i, 1, n + 1) {
cin >> a[i];
}
REP (i, 1, n + 1) {
bad[i] = 0;
}
ptr = n + 1;
incre(a[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], i, dq.front());
} else {
bad[i] = 1;
}
}
if (bad[n]) {
cout << -1 << '\n';
} else {
cout << st[n] << '\n';
ans.clear();
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: 2ms
memory: 25908kb
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 6 5 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 618 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 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...