QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#457142	#964. Excluded Min	541forever	WA	11ms	63496kb	C++20	7.8kb	2024-06-29 08:23:10	2024-06-29 08:23:14

Judging History

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

[2024-06-29 08:23:14]
评测

测评结果：WA
用时：11ms
内存：63496kb

查看

[2024-06-29 08:23:10]
提交

answer

#include <bits/stdc++.h>
#define TEST(x) freopen(x ".in", "r", stdin), freopen("test.out", "w", stdout)
#define debug std::cerr << "Running on " << __FUNCTION__ << ' ' << __LINE__ << std::endl;
#define Ptn std::pair
#define fi first
#define se second
#define Arr std::vector
#define eb emplace_back
#define pb push_back
const int N = 5e5 + 5;
const int M = 5e5;
const int INF = 0x3f3f3f3f;
int n, q, a[N], ans[N], c[N], vis[N];
std::array<int, 3> Q[N];
Arr<int> pos[N];

inline int lowbit(int x) {return x & (-x);}

void add(int x, int y) { for (; x <= n; x += lowbit(x)) c[x] += y; }

int qry(int x)
{
    int res = 0; for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

#define lc (p << 1)
#define rc (p << 1 | 1)

struct SegmentTree1
{
    Ptn<int, int> mx[N << 2], mxr[N << 2], mnl[N << 2];
    int tag[N << 2];

    void upd(int p) 
    {
        mx[p] = std::max(mx[lc], mx[rc]); 
        mxr[p] = std::max(mxr[lc], mxr[rc]);
        mnl[p] = std::min(mnl[lc], mnl[rc]);
    }

    void pushdown(int p)
    {
        if (tag[p])
        {
            int t = tag[p]; tag[p] = 0;
            tag[lc] += t, tag[rc] += t;
            mx[lc].fi += t, mx[rc].fi += t;
        }
    }

    void build(int p = 1, int L = 1, int R = q)
    {
        tag[p] = 0;
        if (L == R) return mxr[p] = mx[p] = {-INF, L}, mnl[p] = {INF, L}, void();
        int mid = (L + R) >> 1;
        build(lc, L, mid), build(rc, mid + 1, R);
        upd(p);
    }

    void change(int x, std::array<int, 3> y, int z = -INF, int p = 1, int L = 1, int R = q)
    {
        if (L == R) return mx[p] = {(z == -INF) ? (y[1] - y[0] + 1) : z, x}, mxr[p] = {y[1], x}, mnl[p] = {y[0], x}, void();
        int mid = (L + R) >> 1; pushdown(p);
        if (x <= mid) change(x, y, z, lc, L, mid);
        else change(x, y, z, rc, mid + 1, R);
        upd(p);
    }

    int qryL(int x, int p = 1, int L = 1, int R = q)
    {
        if (mxr[p].fi < x) return -1;
        if (L == R) return L;
        int mid = (L + R) >> 1; pushdown(p);
        if (mxr[lc].fi >= x) return qryL(x, lc, L, mid);
        else return qryL(x, rc, mid + 1, R);
    }

    int qryR(int x, int p = 1, int L = 1, int R = q)
    {
        if (mnl[p].fi > x) return -1;
        if (L == R) return L;
        int mid = (L + R) >> 1; pushdown(p);
        if (mnl[rc].fi <= x) return qryR(x, rc, mid + 1, R);
        else return qryR(x, lc, L, mid);
    }

    void modify(int l, int r, int x, int p = 1, int L = 1, int R = q)
    {
        if (l <= L && R <= r) return tag[p] += x, mx[p].fi += x, void();
        int mid = (L + R) >> 1; pushdown(p);
        if (l <= mid) modify(l, r, x, lc, L, mid);
        if (r >= mid + 1) modify(l, r, x, rc, mid + 1, R);
        upd(p);
    }

    int nxt(int x, int p = 1, int L = 1, int R = q)
    {
        if (mxr[p].fi < Q[x][1]) return q;
        if (L == R) return L;
        int mid = (L + R) >> 1; pushdown(p);
        if (x <= mid)
        {
            if (mxr[lc].fi >= Q[x][1]) return nxt(x, lc, L, mid);
            else return nxt(x, rc, mid + 1, R);
        }
        else return nxt(x, rc, mid + 1, R);
    }

    int pre(int x, int p = 1, int L = 1, int R = q)
    {
        // printf("pre : %d %d %d %d\n", x, p, L, R); 
        if (mnl[p].fi > Q[x][0]) return 0;
        if (L == R) return Q[L][1]; 
        int mid = (L + R) >> 1; pushdown(p);
        if (x >= mid + 1) 
        {
            if (mnl[rc].fi <= Q[x][0]) return pre(x, rc, mid + 1, R);
            else return pre(x, lc, L, mid); 
        }
        else return pre(x, lc, L, mid);
    }
    
    void del(int x, int p = 1, int L = 1, int R = q)
    {
        if (L == R) return mxr[p] = mx[p] = {-INF, L}, mnl[p] = {INF, L}, void();
        int mid = (L + R) >> 1; pushdown(p);
        if (x <= mid) del(x, lc, L, mid);
        else del(x, rc, mid + 1, R);
        upd(p);
    }

} T1;

struct SegmentTree2
{
    Ptn<int, int> mx[N << 2];

    void upd(int p) { mx[p] = std::max(mx[lc], mx[rc]); }

    void build(int p = 1, int L = 1, int R = q)
    {
        if (L == R) return mx[p] = {-INF, L}, void();
        int mid = (L + R) >> 1;
        build(lc, L, mid), build(rc, mid + 1, R);
        upd(p);
    }

    void change(int x, int y, int p = 1, int L = 1, int R = q)
    {
        if (L == R) return mx[p] = {y, x}, void();
        int mid = (L + R) >> 1;
        if (x <= mid) change(x, y, lc, L, mid);
        else change(x, y, rc, mid + 1, R);
        upd(p);
    }

    Ptn<int, int> qry(int l, int r, int p = 1, int L = 1, int R = q)
    {
        if (l <= L && R <= r) return mx[p];
        int mid = (L + R) >> 1;
        Ptn<int, int> res = {-INF, -INF};
        if (l <= mid) res = qry(l, r, lc, L, mid);
        if (r >= mid + 1) res = std::max(res, qry(l, r, rc, mid + 1, R));
        return res;
    }

    void del(int x, int p = 1, int L = 1, int R = q)
    {
        if (L == R) return mx[p] = {-INF, L}, void();
        int mid = (L + R) >> 1;
        if (x <= mid) del(x, lc, L, mid);
        else del(x, rc, mid + 1, R);
        upd(p);
    }
} T2;
#undef lc 
#undef rc

signed main()
{
    // TEST("set3");
    // freopen("a.in", "r", stdin);
    // freopen("me.out", "w", stdout);
    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
    std::cin >> n >> q; for (int i = 1; i <= n; i++) std::cin >> a[i], pos[a[i]].eb(i);
    for (int i = 1; i <= q; i++)
    {
        int l, r; std::cin >> l >> r;
        Q[i] = {l, -r, i};
    }
    std::sort(Q + 1, Q + q + 1); for (int i = 1; i <= q; i++) Q[i][1] = -Q[i][1];
    // for (int i = 1; i <= q; i++) printf("%d : %d ~ %d = %d\n", i, Q[i][0], Q[i][1], Q[i][2]);
    T1.build(); T2.build(); int R = 0;
    for (int i = 1; i <= q; i++) if (Q[i][1] > R) vis[i] = 1, T1.change(i, Q[i]), R = Q[i][1];
    for (int i = 1; i <= q; i++) if (!vis[i]) T2.change(i, Q[i][1]);
    // for (int i = 1; i <= q; i++) printf("%d : %d\n", i, vis[i]); puts("");
    for (int t = M; t >= 0; t--)
    {
        // std::cerr << t << std::endl;
        for (auto p : pos[t]) 
        {
            add(p, 1); 
            // debug
            Ptn<int, int> range = {T1.qryL(p), T1.qryR(p)}; 
            // debug
            // std::cerr << range.fi << ' ' << range.se << std::endl;
            if (range.fi == -1 || range.se == -1 || Q[range.fi][0] > p || Q[range.se][1] < p) continue;
            // std::cerr << range.fi << ' ' << range.se << std::endl; debug
            // printf("%d %d\n", t, p);
            // printf("%d ~ %d\n", range.fi, range.se);
            T1.modify(range.fi, range.se, -1); 
            // debug
        }
        while (T1.mx[1].fi >= t)
        {
            // printf("mx : %d %d\n", T1.mx[1].fi, T1.mx[1].se);
            int id = T1.mx[1].se;
            T1.del(id); 
            int nxtid = T1.nxt(id), prer = T1.pre(id);
            // printf("%d   id1 : %d %d\n", t, id, Q[id][2]);
            // printf("[] %d %d\n", nxtid, prer);
            ans[Q[id][2]] = t;
            do 
            {
                auto ng = T2.qry(id, nxtid);
                // printf("id = %d nxtid = %d prer = %d %d %d\n", id, nxtid, prer, ng.fi, ng.se);
                if (ng.fi > prer) 
                {
                    int F = Q[ng.se][1] - Q[ng.se][0] + 1 - (qry(Q[ng.se][1]) - qry(Q[ng.se][0] - 1));
                    // printf("t = %d : %d [][][] %d : %d\n", t, ng.se, Q[ng.se][2], F);
                    T1.change(ng.se, Q[ng.se], F); T2.del(ng.se);
                    nxtid = ng.se;
                    // printf("id2 : %d %d\n", ng.se, Q[ng.se][2]);
                } else nxtid = -1;
            } while (nxtid != -1);
        }
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    std::cerr << "Time = " << (double)clock() / CLOCKS_PER_SEC << "s" << std::endl;
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 57356kb

input:

output:

3
1
0

result:

ok 3 number(s): "3 1 0"

Test #2:

score: 0

Accepted

time: 4ms

memory: 55204kb

input:

output:

0
3

result:

ok 2 number(s): "0 3"

Test #3:

score: 0

Accepted

time: 4ms

memory: 55304kb

input:

10 10
3 0 3 3 9 7 9 6 0 7
3 3
9 9
4 6
1 9
3 4
2 4
7 10
3 7
5 7
2 7

output:

result:

ok 10 numbers

Test #4:

score: 0

Accepted

time: 0ms

memory: 55200kb

input:

10 10
3 0 0 0 5 1 1 1 2 1
1 2
8 8
5 7
1 7
2 2
1 5
5 6
4 6
3 10
6 8

output:

result:

ok 10 numbers

Test #5:

score: 0

Accepted

time: 11ms

memory: 51776kb

input:

100 100
15 82 7 39 63 55 64 99 71 63 32 99 67 94 3 43 15 75 45 55 53 4 35 36 15 40 82 20 62 43 6 83 27 95 27 45 98 44 35 98 39 7 17 32 76 7 40 16 40 63 13 8 22 27 11 12 61 14 19 45 100 97 90 88 22 59 25 63 4 25 65 16 22 92 84 44 99 66 89 26 93 97 35 97 92 1 32 40 97 97 78 43 7 12 23 53 61 74 33 90
1...

output:

result:

ok 100 numbers

Test #6:

score: 0

Accepted

time: 3ms

memory: 63496kb

input:

100 100
17 86 33 8 11 27 8 11 13 9 3 43 11 23 26 42 44 12 44 12 15 0 75 51 72 5 49 2 40 57 24 47 39 42 4 5 6 52 3 2 42 19 62 33 24 22 16 69 4 33 44 70 29 11 2 2 58 9 6 10 25 10 33 26 17 3 14 0 48 7 48 51 0 39 54 37 14 9 3 85 18 4 25 9 2 0 39 8 17 13 25 45 10 39 12 18 9 5 66 6
13 89
10 90
42 67
43 52...

output:

result:

ok 100 numbers

Test #7:

score: -100

Wrong Answer

time: 4ms

memory: 61336kb

input:

100 100
6 1 1 5 13 11 35 5 3 2 0 4 0 9 1 2 3 3 19 1 7 9 7 11 7 8 10 18 28 17 31 2 4 8 2 3 3 2 22 4 9 4 7 2 9 15 8 2 3 19 5 24 3 10 11 5 9 20 8 4 11 10 18 9 13 34 5 34 2 9 24 6 21 16 6 12 26 2 2 2 6 11 2 14 3 8 2 12 2 19 8 3 18 23 5 21 23 8 4 0
44 67
25 74
24 79
59 73
4 81
42 66
48 55
15 38
35 63
16 ...

output:

result:

wrong answer 29th numbers differ - expected: '0', found: '3'