QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104347#6400. Game: Celestemaomao90TL 0ms20832kbC++174.2kb2023-05-10 11:04:102023-05-10 11:04:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-10 11:04:13]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:20832kb
  • [2023-05-10 11:04:10]
  • 提交

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) {
    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
    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';
            dfs(n);
            for (int i : ans) {
                cout << i << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

详细

Test #1:

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

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

result: