QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130235 | #3300. Cactus Competition | Jryno1 | WA | 2ms | 11956kb | C++14 | 2.7kb | 2023-07-23 18:34:27 | 2023-07-23 18:34:31 |
Judging History
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'