QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369700 | #3300. Cactus Competition | zwh2008 | WA | 2ms | 9828kb | C++14 | 1.5kb | 2024-03-28 16:44:24 | 2024-03-28 16:44:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,a[N],b[N],c1[N],c2[N],pre[N],suf[N],mxa[18][N],mxb[18][N];
ll ans;
int aska(int l,int r){int k=__lg(r-l+1);return max(mxa[k][l],mxa[k][r-(1<<k)+1]);}
int askb(int l,int r){int k=__lg(r-l+1);return max(mxb[k][l],mxb[k][r-(1<<k)+1]);}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m,pre[0]=suf[n+1]=2e9;
for(int i=1;i<=n;i++)cin>>a[i],mxa[0][i]=a[i],pre[i]=min(pre[i-1],a[i]);
for(int i=n;i;i--)suf[i]=min(suf[i+1],a[i]);
for(int i=1;i<=m;i++)cin>>b[i],mxb[0][i]=b[i];
for(int i=1;1<<i<=n;i++)for(int j=1;j<=n-(1<<i)+1;j++)mxa[i][j]=max(mxa[i-1][j],mxa[i-1][j+(1<<i-1)]);
for(int i=1;1<<i<=m;i++)for(int j=1;j<=m-(1<<i)+1;j++)mxb[i][j]=max(mxb[i-1][j],mxb[i-1][j+(1<<i-1)]);
int mn=*min_element(b+1,b+m+1),mx=*max_element(b+1,b+m+1);
for(int i=1;i<=n;i++) {
int l=1,r=m,mid,res=0,val,f,g;
while(l<=r)mid=l+r>>1,askb(1,mid)+res<0?l=mid+1,res=mid:r=mid-1;
val=pre[res],l=1,r=i,f=i+1;
while(l<=r)mid=l+r>>1,aska(mid,i)+val<0?r=mid-1,f=mid:l=mid+1;
c1[f]++,c1[i+1]--,l=1,r=m,res=m+1;
while(l<=r)mid=l+r>>1,askb(mid,m)+res<0?r=mid-1,res=mid:l=mid+1;
val=suf[res],l=i,r=n,g=i-1;
while(l<=r)mid=l+r>>1,aska(i,mid)+val<0?l=mid+1,g=mid:r=mid-1;
c2[i]++,c2[g+1]--;
}
for(int i=1;i<=n;i++)c1[i]+=c1[i-1],c2[i]+=c2[i-1];
for(int i=n,j=n+1,s=0;i;i--) {
if(a[i]+mx<0)j=i+1,s=0;
if(a[i]+mn>=0) {
for(int k=i;k<j;k++)s+=!c2[k];
j=i;
}ans+=(!c1[i])*s;
}cout<<ans<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9768kb
input:
3 3 -1 0 1 -1 0 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9724kb
input:
3 3 -1 0 1 1 0 1
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9828kb
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: -100
Wrong Answer
time: 0ms
memory: 9800kb
input:
10 10 923415743 -503391272 885740174 329644337 -693052351 -53764994 731859967 -834732760 -57751504 151969590 553689579 313784278 -12090771 921222379 -378313551 819586787 -373658045 559813071 671861309 268258615
output:
0
result:
wrong answer 1st lines differ - expected: '13', found: '0'