QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#425431	#964. Excluded Min	Nt_Yester	WA	8ms	27460kb	C++14	5.4kb	2024-05-30 10:59:34	2024-05-30 10:59:34

Judging History

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

[2024-05-30 10:59:34]
评测

测评结果：WA
用时：8ms
内存：27460kb

查看

[2024-05-30 10:59:34]
提交

answer

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

#define N 500001

using namespace std;
int n,q,a[N],ans[N];
vector<int> vpos[N];

int c[N];

int lowbit(int x) { return x&-x; }
void upd(int x,int k) { for (int i=x;i<=n;i+=lowbit(i)) c[i]+=k; }
int ask(int x) { int res=0; for (int i=x;i;i-=lowbit(i)) res+=c[i]; return res; }

struct Q {
    int l,r,id;

    bool operator<(Q t) { return l^t.l?l<t.l:r>t.r; }
}_q[N];

struct Q1 {
    int l,r,tid;

    bool operator<(Q1 t) { return l^t.l?l<t.l:r<t.r; }
};
vector<Q1> st;

struct Tree1 {
    struct Tree {
        int r,id;
    
        bool operator<(Tree tmp) { return r<tmp.r; }
    }t[N<<2];
    vector<Tree> v[N];

    void build(int x,int l,int r) {
        t[x].r=-1;
        if (l==r) return;
        int mid=(l+r>>1);
        build(x<<1,l,mid); build(x<<1|1,mid+1,r);
    }

    void upd(int x,int l,int r,int pos,int R,int id) {
        if (l==r) return t[x]={R,id},void();
        int mid=(l+r>>1);
        if (pos<=mid) upd(x<<1,l,mid,pos,R,id);
        else upd(x<<1|1,mid+1,r,pos,R,id);
        t[x].r=max(t[x<<1].r,t[x<<1|1].r);
    }

    Q1 ask(int x,int l,int r,int L,int R,int pos) {
        if (L<=l and r<=R) {
            if (l==r) return Q1{l,t[x].r,t[x].id};
            int mid=(l+r>>1);
            if (t[x<<1].r>pos) return ask(x<<1,l,mid,L,R,pos);
            else if (t[x<<1|1].r>pos) return ask(x<<1|1,mid+1,r,L,R,pos);
            return {(int)1e9,0,0};
        }
        int mid=(l+r>>1);
        if (L<=mid and t[x<<1].r>pos) return ask(x<<1,l,mid,L,R,pos);
        else if (R>mid and t[x<<1|1].r>pos) return ask(x<<1|1,mid+1,r,L,R,pos);
        return {(int)1e9,0,0};
    }
}t1;

struct Tree2 {
    struct Tree { int val,tag; }t[N<<2];

    void pushdown(int x) {
        if (t[x].tag) {
            t[x<<1].val+=t[x].tag,t[x<<1|1].val+=t[x].tag;
            t[x<<1].tag+=t[x].tag,t[x<<1|1].tag+=t[x].tag;
            t[x].tag=0;
        }
    }

    void updf(int x,int l,int r,int pos,int k) {
        if (l==r) return t[x].val=k,void();
        int mid=(l+r>>1); pushdown(x);
        if (pos<=mid) updf(x<<1,l,mid,pos,k);
        else updf(x<<1|1,mid+1,r,pos,k);
        t[x].val=max(t[x<<1].val,t[x<<1|1].val);
    }

    void upd(int x,int l,int r,int L,int R,int k) {
        if (L<=l and r<=R) return t[x].val+=k,t[x].tag+=k,void();
        int mid=(l+r>>1); pushdown(x);
        if (L<=mid) upd(x<<1,l,mid,L,R,k);
        if (R>mid) upd(x<<1|1,mid+1,r,L,R,k);
        t[x].val=max(t[x<<1].val,t[x<<1|1].val);
    }

    int ask(int x,int l,int r,int k) {
        if (l==r) {
            ans[_q[l].id]=k,t[x].val=-1;
            return l;
        }
        int mid=(l+r>>1),res=0; pushdown(x);
        if (t[x<<1].val>=k) res=ask(x<<1,l,mid,k);
        else if (t[x<<1|1].val>=k) res=ask(x<<1|1,mid+1,r,k);
        t[x].val=max(t[x<<1].val,t[x<<1|1].val); 
        return res;
    }
}t2;

int findl(int x) {
    int l=0,r=st.size()-1,res=-1;
    while (l<=r) {
        int mid=(l+r>>1);
        if (st[mid].r>=x) res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

int findr(int x) {
    int l=0,r=st.size()-1,res=-1;
    while (l<=r) {
        int mid=(l+r>>1);
        if (st[mid].l<=x) res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}

int main() {
    scanf("%d%d",&n,&q); int maxn=5e5;
    for (int i=1;i<=n;i++) scanf("%d",a+i),maxn=max(maxn,a[i]),vpos[a[i]].push_back(i),upd(i,1);
    for (int i=1;i<=q;i++) scanf("%d%d",&_q[i].l,&_q[i].r),_q[i].id=i;
    sort(_q+1,_q+q+1);
    Q lst;
    t1.build(1,1,n);
    for (int i=1;i<=q;i++) {
        if (i==1 or _q[i].r>lst.r) {
            lst=_q[i],st.push_back({_q[i].l,_q[i].r,i});
            t2.updf(1,1,q,i,ask(_q[i].r)-ask(_q[i].l-1));
        } else {
            t1.v[_q[i].l].push_back({_q[i].r,i});
        }
    }
    for (int i=1;i<=n;i++) {
        sort(t1.v[i].begin(),t1.v[i].end());
        if (!t1.v[i].empty()) 
            t1.upd(1,1,n,i,t1.v[i].back().r,t1.v[i].back().id),t1.v[i].pop_back();
    }
    for (int i=maxn;i>=0;i--) { 
        for (int j:vpos[i]) {
            upd(j,-1);
            int l=findl(j),r=findr(j);
            if (l>r or l==-1 or r==-1) continue;
            l=st[l].tid,r=st[r].tid;
            t2.upd(1,1,q,l,r,-1);
        }
        while (t2.t[1].val>=i) {
            int x=t2.ask(1,1,q,i);
            Q1 tmp={_q[x].l,_q[x].r,x};
            auto It=lower_bound(st.begin(),st.end(),tmp);
            int it=It-st.begin(); Q1 pre,nxt;
            if (!it) pre={0,0,0};
            else pre=st[it-1];
            if (it==st.size()-1) nxt={n+1,n+1,n};
            else nxt=st[it+1];
            st.erase(It);
            while (pre<nxt) {
                Q1 now=t1.ask(1,1,n,pre.l,n,pre.r);
                if (nxt.l<=now.l and now.r<=nxt.r) break;
                t2.updf(1,1,q,now.tid,ask(now.r)-ask(now.l-1));
                if (t1.v[now.l].empty()) t1.upd(1,1,n,now.l,-1,-1);
                else t1.upd(1,1,n,now.l,t1.v[now.l].back().r,t1.v[now.l].back().id),t1.v[now.l].pop_back();
                st.insert(lower_bound(st.begin(),st.end(),now),now);
                pre=now;
            }
        }
    }
    for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}
/*
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
*/

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 6ms

memory: 27400kb

input:

output:

3
1
0

result:

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

Test #2:

score: 0

Accepted

time: 4ms

memory: 27416kb

input:

output:

0
3

result:

ok 2 number(s): "0 3"

Test #3:

score: 0

Accepted

time: 4ms

memory: 27412kb

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: 8ms

memory: 27272kb

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: 4ms

memory: 27460kb

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: -100

Wrong Answer

time: 4ms

memory: 27332kb

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:

wrong answer 29th numbers differ - expected: '22', found: '23'