90pts TLE on#10 玄关求条
查看原帖
90pts TLE on#10 玄关求条
1038207
SolRise楼主2024/7/15 11:03
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp,mp1;//mp离散化,mp1逆映射
long long s[4001][4001],a[1001],b[1001],c[1001],d[1001],ans;
signed main()
{
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{	
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		mp[a[i]]=mp[b[i]]=mp[c[i]]=mp[d[i]]=-1;
	}
	int num=0;
	for(map<int,int>::iterator x=mp.begin();x!=mp.end();x++)
	{
		x->second=++num;
		mp1[x->second]=x->first;
	}
	for(int i=1;i<=n;i++)
	{
		s[mp[a[i]]][mp[b[i]]]++;
		s[mp[c[i]]][mp[b[i]]]--;
		s[mp[a[i]]][mp[d[i]]]--;
		s[mp[c[i]]][mp[d[i]]]++;
	}//差分
	for(int i=1;i<=num;i++)
		for(int j=1;j<=num;j++)
			s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
	for(int i=1;i<num;i++)
		for(int j=1;j<num;j++)
			if(s[i][j])
				ans+=(mp1[i+1]-mp1[i])*(mp1[j+1]-mp1[j]);
	cout<<ans;
	return 0;
}

用map离散化,时间应该是 O(n2)O(n^2),但还是T了,求卡常

2024/7/15 11:03
加载中...