记得开long long

#21 Hack数据

输入

CPP

4 6
1000000000 1000000000 1000000000 1000000000
1000000000 1 4
1000000000 1 4
1000000000 1 4
1000000000 1 4
1000000000 1 4
1000000000 1 4

输出

CPP

-1
2

如果不开long long，在二分第一步check(3)时前缀和为3e9，超int空间了，会变成负数，导致答案是6。但是，我们机房，有一个非常牛的大佬用神奇的操作，~~负负得正~~，没开long long过了神奇代码：

CPP


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000010;
int n,m;
int a[N],c[N],num[N],nt[N],ed[N];

bool cxcheck(int x)
{
	memset(c,0,sizeof(c));
	for(int i=1;i<=x;++i)
	{
		c[nt[i]]-=num[i];
		c[ed[i]+1]+=num[i];
	}
	for(int i=1;i<=n;++i)
	{
		c[i]+=c[i-1];
		if(a[i]+c[i]<0) return false;
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&num[i],&nt[i],&ed[i]);
	if(cxcheck(m)) {cout<<0;return 0;}
	int l=1,r=m;
	while(l<r)
 	{
	 	int mid=(l+r)>>1;
	 	if(!cxcheck(mid)) r=mid;
	 	else l=mid+1;
 	}
	cout<<-1<<endl<<l;

	return 0;
}

讨论操作

回复

相关推荐

记得开long long