QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#774317#9786. Magical Bagsucup-team4454#WA 7ms34396kbC++143.9kb2024-11-23 12:58:032024-11-23 12:58:04

Judging History

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

  • [2024-11-23 12:58:04]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:34396kb
  • [2024-11-23 12:58:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,flg=0;
    char c=getchar();
    while(c<'0'||c>'9')flg|=c=='-',c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',c=getchar();
    return flg?-ret:ret;
}
inline void write(int x,bool flg){
    char a[21];
    if(!x)putchar('0');
    if(x<0)putchar('-'),x=-x;
    int cnt=0;
    while(x){
        a[++cnt]=x%10+'0';
        x/=10;
    }
    while(cnt)putchar(a[cnt--]);
    putchar(flg?'\n':' ');
    return ;
}
#define maxn 400010
int n,a[maxn],b[maxn],A[maxn],B[maxn];
int l[maxn],r[maxn];
vector<int> v[maxn];
int la[maxn<<2],ra[maxn<<2],lb[maxn<<2],rb[maxn<<2];
void build(int L,int R,int p){
    //cout<<L<<" "<<R<<endl;
    if(L==R){
        la[p]=l[a[L]];
        ra[p]=r[a[L]];
        lb[p]=l[b[L]];
        rb[p]=r[b[L]];
        return ;
    }
    int mid(L+R>>1);
    build(L,mid,p<<1);
    build(mid+1,R,p<<1|1);
    la[p]=max(la[p<<1],la[p<<1|1]);
    ra[p]=min(ra[p<<1],ra[p<<1|1]);
    lb[p]=max(lb[p<<1],lb[p<<1|1]);
    rb[p]=min(rb[p<<1],rb[p<<1|1]);
    return ;
}
void query1(int l_,int r_,int L,int R,int &La,int &Ra,int p){
    if(L<=l_&&r_<=R){
        La=max(La,la[p]);
        Ra=min(Ra,ra[p]);
        return ;
    }
    int mid(l_+r_>>1);
    if(L<=mid)return query1(l_,mid,L,R,La,Ra,p<<1);
    if(R>mid)return query1(mid+1,r_,L,R,La,Ra,p<<1|1);
    return ;
}
void query2(int l_,int r_,int L,int R,int &Lb,int &Rb,int p){
    if(L<=l_&&r_<=R){
        Lb=max(Lb,lb[p]);
        Rb=min(Rb,rb[p]);
        return ;
    }
    int mid(l_+r_>>1);
    if(L<=mid)return query2(l_,mid,L,R,Lb,Rb,p<<1);
    if(R>mid)return query2(mid+1,r_,L,R,Lb,Rb,p<<1|1);
    return ;
}
void modify1(int l_,int r_,int x,int p){    
    if(l_==r_){
        la[p]=l[a[l_]];
        ra[p]=r[a[l_]];
        return ;
    }
    int mid(l_+r_>>1);
    if(x<=mid)modify1(l_,mid,x,p<<1);
    else modify1(mid+1,r_,x,p<<1|1);
    la[p]=max(la[p<<1],la[p<<1|1]);
    ra[p]=min(ra[p<<1],ra[p<<1|1]);
    return ;
}
void modify2(int l_,int r_,int x,int p){
    if(l_==r_){
        lb[p]=l[b[l_]];
        rb[p]=r[b[l_]];
        return ;
    }
    int mid(l_+r_>>1);
    if(x<=mid)modify2(l_,mid,x,p<<1);
    else modify2(mid+1,r_,x,p<<1|1);
    lb[p]=max(lb[p<<1],lb[p<<1|1]);
    rb[p]=min(rb[p<<1],rb[p<<1|1]);
    return ;
}
int id1[maxn],id2[maxn],fl[maxn],id[maxn];
int main(){
    n=read();
    int ans=0;
    for(int i=1;i<=n;i++){
        int k=read();
        l[i]=1e9,r[i]=0;
        for(int j=1;j<=k;j++){
            int x=read();
            l[i]=min(l[i],x);
            r[i]=max(r[i],x);
            v[i].push_back(x);
        }
        ans+=2-(k==1);
        a[i]=b[i]=id[i]=i;
    }
    sort(a+1,a+n+1,[](int x,int y){
        return r[x]<r[y];
    });
    sort(b+1,b+n+1,[](int x,int y){
        return l[x]<l[y];
    });
    sort(id+1,id+n+1,[](int x,int y){
        return r[x]-l[x]<r[y]-l[y];
    });
    //cout<<"ee"<<endl;
    build(1,n,1);
//    cout<<ans<<endl;
    for(int i=1,mx=0;i<=n;i++){
        if(l[a[i]]<mx){
            fl[a[i]]=1;
        }
        mx=max(mx,l[a[i]]);
    }
    for(int i=1;i<=n;i++){
        A[i]=r[a[i]];
        B[i]=l[b[i]];
        id1[a[i]]=i;
        id2[b[i]]=i;
    }
    for(int j=1,i;j<=n;j++){
        i=id[j];//cout<<i<<endl;
        if(l[i]==r[i])continue;
        int L=l[i],R=r[i];
        int pos=lower_bound(A+1,A+n+1,l[i]+1)-A;
        query1(1,n,pos,id1[i],L,R,1);
        pos=lower_bound(B+1,B+n+1,r[i]+1)-B-1;
        query2(1,n,id2[i],pos,L,R,1);
    //    cout<<i<<" "<<L<<" "<<R<<endl;
        for(auto t:v[i]){
            if(L<=t&&t<=R){
                ans--;
                l[i]=r[i]=t;
                modify1(1,n,id1[i],1);
                modify2(1,n,id2[i],1);
                break;
            }
        }
    }write(ans,1);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 7ms
memory: 34340kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 0ms
memory: 34312kb

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #4:

score: 0
Accepted
time: 0ms
memory: 34396kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 34256kb

input:

100
4 372861091 407948190 424244630 359746969
6 568180757 527358812 494745349 665803213 674832670 586694351
4 696340797 775899164 919971335 716827187
4 123145962 344250363 122030550 251739234
4 342654413 368648894 150539766 255189030
1 194505887
3 755984448 736803561 745474041
4 709314938 498953418 ...

output:

160

result:

wrong answer 1st numbers differ - expected: '177', found: '160'