QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#130235#3300. Cactus CompetitionJryno1WA 2ms11956kbC++142.7kb2023-07-23 18:34:272023-07-23 18:34:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 18:34:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11956kb
  • [2023-07-23 18:34:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m,a[maxn],b[maxn],chas[maxn],minval[maxn],pos[maxn],minpos[maxn],sufval[maxn],maxpos[maxn],chae[maxn];
int avlis[maxn],avlie[maxn],maxb,maxa,minb;
bool cmp(int x,int y){return b[x]<b[y];}
//minbpos:the pos of the mininum b[i]
int tr[maxn<<2];
void BT(int x,int l,int r){
    tr[x]=-1e9-1;
    if(l==r)return;
    int mid=(l+r)>>1;
    BT(x<<1,l,mid);
    BT(x<<1|1,mid+1,r);
}
void CT(int x,int l,int r,int pos,int val){
    if(l==r){
        tr[x]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)CT(x<<1,l,mid,pos,val);
    else CT(x<<1|1,mid+1,r,pos,val);
    tr[x]=max(tr[x<<1],tr[x<<1|1]);
}
int QT(int x,int l,int r,int val,int opt){
    if(tr[x]<val){
       if(!opt)return 0;
       else return n+1;
    }
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(!opt){
        if(tr[x<<1|1]>=val)return QT(x<<1|1,mid+1,r,val,opt);
        return QT(x<<1,l,mid,val,opt);
    } else {
        if(tr[x<<1]>=val)return QT(x<<1,l,mid,val,opt);
        return QT(x<<1|1,mid+1,r,val,opt);
    }
    return -1;
}
int main(){
    cin>>n>>m;
    maxb=maxa=-1e9-1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxa=max(maxa,a[i]);
    sufval[m+1]=minval[0]=1e9+1;
    for(int i=1;i<=m;i++){
        scanf("%d",&b[i]);
        minval[i]=min(minval[i-1],b[i]);
        pos[i]=i;
        maxb=max(maxb,b[i]);
        minb=min(minb,b[i]);
    }
    for(int i=m;i>=1;i--)sufval[i]=min(sufval[i+1],b[i]);
    sort(pos+1,pos+1+m,cmp);
    sort(b+1,b+1+m);
    minpos[m]=maxpos[m]=pos[m];
    for(int i=m-1;i>=1;i--)minpos[i]=min(minpos[i+1],pos[i]),maxpos[i]=max(maxpos[i+1],pos[i]);
    BT(1,1,n);
    for(int i=1;i<=n;i++){
        int yval=minval[minpos[lower_bound(b+1,b+1+m,-a[i])-b]];
        if(a[i]+yval<0){
            int p=QT(1,1,n,-yval,0);
            chas[p+1]++,chas[i+1]--;
        }
        CT(1,1,n,i,a[i]); 
    } 
    BT(1,1,n);
    for(int i=n;i>=1;i--){
        int yval=sufval[maxpos[lower_bound(b+1,b+1+m,-a[i])-b]];
        //cout<<yval<<endl;
        if(a[i]+yval<0){
            int p=QT(1,1,n,-yval,1);
            chae[i]++,chae[p]--;
        }
        CT(1,1,n,i,a[i]);
    }
    int now=0;
    for(int i=1;i<=n;i++)now+=chas[i],avlis[i]=!now;
    now=0;
    for(int i=1;i<=n;i++)now+=chae[i],avlie[i]=!now;
    for(int i=n;i>=1;i--)avlie[i]+=avlie[i+1];
    long long ans=0,sts=0,fl=0;
    for(int i=1;i<=n;i++){
        if(a[i]+maxb<0){
            sts=0;
            fl=0;
            continue;
        }
        if(avlis[i])sts++;
        if(a[i]+minb>=0){
            ans+=1ll*sts*avlie[i];
            sts=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11956kb

input:

3 3
-1 0 1
-1 0 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 11760kb

input:

3 3
-1 0 1
1 0 1

output:

5

result:

ok single line: '5'

Test #3:

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

input:

10 10
145195799 312862766 143966779 -11056226 -503624929 636383890 -182650312 -382759112 -290767690 377894950
-845235881 -418232930 -600566938 -957917357 -181139226 125255273 -175406945 740226783 -750456842 325848662

output:

0

result:

ok single line: '0'

Test #4:

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

input:

10 10
923415743 -503391272 885740174 329644337 -693052351 -53764994 731859967 -834732760 -57751504 151969590
553689579 313784278 -12090771 921222379 -378313551 819586787 -373658045 559813071 671861309 268258615

output:

13

result:

ok single line: '13'

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 11916kb

input:

10 10
-123276196 264891802 609485405 -980113903 152483893 57563748 -454135131 618686452 545983457 236619926
648896419 838269531 -380077537 536463844 89691984 38425645 759165084 325716532 330825142 -472414030

output:

18

result:

wrong answer 1st lines differ - expected: '12', found: '18'