QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-10 16:27:50]
评测

测评结果：TL
用时：2ms
内存：25908kb

查看

[2023-05-10 16:27:46]
提交

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;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 25908kb

input:

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