求助30pts代码
查看原帖
求助30pts代码
297785
mazy楼主2021/7/20 20:37

按照夏令营课上老师的思路写的,但是只有30pts,有WA有RE,调了半天过不去。

感谢大佬帮助。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int MAXN= 2007;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<48||ch>57)		{if(ch=='-') f=-1;ch=getchar();}
	while(ch>=48&&ch<=57)	x=x*10+ch-48,ch=getchar();
	return x*f;
}

int n,a[MAXN][5],dict[MAXN],dtop,diff[MAXN][MAXN];

signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=4;j++)
			dict[++dtop]=a[i][j]=read();

	sort(dict+1,dict+dtop+1);
	int len=unique(dict+1,dict+dtop+1)-dict-1;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=4;j++)
			a[i][j]=lower_bound(dict+1,dict+dtop+1,a[i][j])-dict;
			
	for(int i=1;i<=n;i++)
		for(int j=a[i][1];j<a[i][3];j++)
			diff[j][a[i][4]]++,diff[j][a[i][2]]--;
	
	ll ans=0;
	for(int i=1;i<len;i++)
		for(int j=1;j<len;j++)
			diff[i][j]+=diff[i][j-1];
	
	for(int i=1;i<len;i++)
		for(int j=1;j<len;j++)
			if(diff[i][j])
				ans+=(ll)(dict[i+1]-dict[i])*(dict[j+1]-dict[j]);
	printf("%lld",ans);
	return 0;
}
2021/7/20 20:37
加载中...