QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369700#3300. Cactus Competitionzwh2008WA 2ms9828kbC++141.5kb2024-03-28 16:44:242024-03-28 16:44:26

Judging History

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

  • [2024-03-28 16:44:26]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9828kb
  • [2024-03-28 16:44:24]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'