QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#101445#3300. Cactus Competition1kriWA 2ms26000kbC++141.7kb2023-04-29 20:05:292023-04-29 20:05:30

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-29 20:05:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:26000kb
  • [2023-04-29 20:05:29]
  • 提交

answer

#include <iostream>
#include <cstdio>
using namespace std;
int n,m;
struct QwQ{
	int n,val[200005];
	int log_2[200005],mn[20][200005],mx[20][200005];
	void init(int _n){
		n=_n;
		for (int i=1;i<=n;i++)scanf("%d",&val[i]);
		for (int i=2;i<=n;i++)log_2[i]=log_2[i/2]+1;
		for (int i=1;i<=n;i++){
			mn[0][i]=val[i];
			mx[0][i]=val[i];
		}
		for (int w=1;w<20;w++)
			for (int i=1;i+(1<<w)-1<=n;i++){
				mn[w][i]=min(mn[w-1][i],mn[w-1][i+(1<<(w-1))]);
				mx[w][i]=max(mx[w-1][i],mx[w-1][i+(1<<(w-1))]);
			}
		return;
	}
	int askmn(int l,int r){
		int w=log_2[r-l+1];
		return min(mn[w][l],mn[w][r-(1<<w)+1]);
	}
	int askmx(int l,int r){
		int w=log_2[r-l+1];
		return max(mx[w][l],mx[w][r-(1<<w)+1]);
	}
}a,b;
int f[200005],t[200005],g[200005];
int sum[200005];
int ans;
int main(){
	cin>>m>>n;
	b.init(m);
	a.init(n);
	int last=-1;
	for (int i=m;i>=1;i--){
		int l=1,r=n,p=0;
		while(l<=r){
			int mid=(l+r)/2;
			if (a.askmn(1,mid)+b.val[i]>=0)p=mid,l=mid+1;
			else r=mid-1;
		}
		if (p==0)continue;
		int val_a=a.askmx(1,p);
		l=i,r=m;
		while(l<=r){
			int mid=(l+r)/2;
			if (val_a+b.askmn(i,mid)>=0)t[i]=mid,l=mid+1;
			else r=mid-1;
		}
		if (p==n||(last!=-1&&t[i]>=last)){
			f[i]=1;
			last=i;
		}
	}
	last=-1;
	for (int i=1;i<=m;i++){
		int l=1,r=n,p=n+1;
		while(l<=r){
			int mid=(l+r)/2;
			if (a.askmn(mid,n)+b.val[i]>=0)p=mid,r=mid-1;
			else l=mid+1;
		}
		if (p==n+1)continue;
		if (p==1||(last!=-1&&a.askmx(p,n)+b.askmn(last,i))>=0){
			g[i]=1;
			last=i;
		}
	}
	for (int i=m;i>=1;i--)sum[i]=sum[i+1]+g[i];
	last=-1;
	for (int i=m;i>=1;i--){
		if (a.askmn(1,n)+b.val[i]>=0)last=i;
		if (f[i]==1&&last!=-1)ans+=sum[last];
	}
	cout<<ans<<endl;
	return 0;
}

詳細信息

Test #1:

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

input:

3 3
-1 0 1
-1 0 1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

3 3
-1 0 1
1 0 1

output:

5

result:

ok single line: '5'

Test #3:

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

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

input:

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

output:

28

result:

wrong answer 1st lines differ - expected: '13', found: '28'