QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#774057#9786. Magical Bagsucup-team4454#WA 6ms32336kbC++143.8kb2024-11-23 11:30:212024-11-23 11:30:21

Judging History

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

  • [2024-11-23 11:30:21]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:32336kb
  • [2024-11-23 11:30:21]
  • 提交

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){    
//    cout<<x<<" "<<l_<<" "<<r_<<endl;
    
    if(l_==r_){
        la[p]=l[a[l_]];
        ra[p]=r[a[l_]];
    //    cout<<la[p]<<" "<<ra[p]<<endl;
        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];
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-(l[i]==r[i]);
        a[i]=b[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];
    });
    //cout<<"ee"<<endl;
    build(1,n,1);
//    cout<<ans<<endl;
    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 i=1;i<=n;i++){
        if(l[i]==r[i])continue;
        int L=l[i],R=r[i];
        int pos=lower_bound(A+1,A+n+1,l[i])-A;
        query1(1,n,pos,id1[i],L,R,1);
        pos=lower_bound(B+1,B+n+1,-r[i])-B;
        query2(1,n,pos,id2[i],L,R,1);
    //    cout<<i<<" "<<L<<" "<<R<<endl;
        for(auto t:v[i]){
            if(t>=L&&t<=R){
                ans--;
                l[i]=r[i]=t;
            //    cout<<id1[i]<<"ee"<<a[id1[i]]<<endl;
                modify1(1,n,id1[i],1);
                modify2(1,n,id2[i],1);
            //    cout<<la[1]<<ra[1]<<endl;
                break;
            }
        }
    }write(ans,1);
    return 0;
}

详细

Test #1:

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

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: 0ms
memory: 30216kb

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: 30288kb

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: 32204kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 6ms
memory: 32336kb

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:

177

result:

ok 1 number(s): "177"

Test #6:

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

input:

100
5 128474911 128789041 128389100 128571722 128449204
4 190783009 179144907 191954599 169739385
7 922968028 923017780 923012667 922993373 923012653 923010830 922983606
1 399117777
8 693609160 693615962 692956804 692902832 694104582 693605539 693750551 692909362
4 133590022 156691169 120354087 1477...

output:

175

result:

ok 1 number(s): "175"

Test #7:

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

input:

100
3 667874577 779650612 311873157
4 315088665 510831928 558038267 371108692
9 755153639 761562353 770756971 766146687 755341778 756786965 752029435 762376276 769269467
6 104846116 127832365 303763622 308914288 193368850 212600340
4 278400790 520739777 691975492 363532266
3 882063076 834874749 8790...

output:

188

result:

ok 1 number(s): "188"

Test #8:

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

input:

100
3 906356952 850278493 852337285
4 171262913 167082071 210705401 185031512
7 802495630 790288362 821278829 774987331 774050880 798490416 758938148
5 15709100 243583562 406822217 439043410 105298894
3 615900896 610909553 657678763
4 829696557 810959924 841612668 819869747
6 853997379 864469575 881...

output:

180

result:

ok 1 number(s): "180"

Test #9:

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

input:

100
4 364081200 540650381 353768306 122255830
7 936882622 937778158 941372288 943745873 947703805 938067346 944019473
7 598655091 679073706 723959930 579018281 860392698 852744534 665808681
1 557290205
3 838323287 764154463 864559801
4 952241609 888202173 792726290 886689636
6 653946054 841409940 83...

output:

175

result:

ok 1 number(s): "175"

Test #10:

score: -100
Wrong Answer
time: 3ms
memory: 32276kb

input:

100
1 440195292
6 859787120 847131414 854112709 869067609 839981608 845676179
5 206450888 209708811 207370111 201853766 207539046
1 555976272
1 938758019
1 413646308
9 252799098 254947888 265345550 249752370 261338550 251583211 248642444 266900460 261558897
5 83936282 116530372 99708225 112074514 96...

output:

148

result:

wrong answer 1st numbers differ - expected: '151', found: '148'