AcWing 759. 格子染色
原题链接
中等
作者:
术
,
2021-01-04 20:54:50
,
所有人可见
,
阅读 451
离散化加差分
未完全通过!!!
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=10005;
int b[N][N];
int a[N][N];
int s[N][N];
vector<int> alls;
typedef pair<int,int> PII;
vector<PII> col;
int find(int x)
{
int l=0,r=alls.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(alls[mid]>=x)
r=mid;
else
l=mid+1;
}
return l+1;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
x1+=1e9;
x2+=1e9;
y1+=1e9;
y2+=1e9;
if(x2<x1||y2<y1)
{
swap(x1,x2);
swap(y1,y2);
}
col.push_back({x1,y1});
col.push_back({x2,y2});
for(int j=x1; j<=x2; j++)
{
alls.push_back(j);
}
for(int k=y1; k<=y2; k++)
{
alls.push_back(k);
}
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i=0; i<alls.size(); i++)
{
//cout<<alls[i]<<" ";
}
// cout<<endl;
for(int i=0; i<col.size()-1; i+=2)
{
int x1=find(col[i].first);
int y1=find(col[i].second);
int x2=find(col[i+1].first);
int y2=find(col[i+1].second);
//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
b[x1][y1]+=1;
b[x1][y2+1]-=1;
b[x2+1][y1]-=1;
b[x2+1][y2+1]+=1;
}
for(int i=1; i<=alls.size(); i++)
{
for(int j=1; j<=alls.size(); j++)
{
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
//cout<<a[i][j]<<" ";
}
//cout<<endl;
}
for(int i=1; i<=alls.size(); i++)
{
for(int j=1; j<=alls.size(); j++)
{
if(a[i][j]>1)
a[i][j]=1;
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
cout<<s[alls.size()][alls.size()];
//cout << "Hello world!" << endl;
return 0;
}