Cod sursa(job #752130)

Utilizator danalex97Dan H Alexandru danalex97 Data 27 mai 2012 21:09:37
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream F("dreptunghiuri3.in");
ofstream G("dreptunghiuri3.out");

#define Dmax 1011

#define x first
#define y second
typedef pair<int,int> Point;

Point First[Dmax*10],Second[Dmax*10];
int Value[Dmax*10];
int N,M,K;

int Coord[Dmax*100],Co;
int Coord2[Dmax*100];
int Normx[Dmax*100],Nbrx;
int Normy[Dmax*100],Nbry;

int Val;
int Max;
long long Arie;
int Mat[Dmax*10][Dmax*10];

inline int max(int a,int b)
{ return ( a>b ) ? a : b; }

inline int min(int a,int b)
{ return ( a>b ) ? a : b; }

inline int Calc(int x,int y)
{ return (Normx[x+1]-Normx[x])*(Normy[y+1]-Normy[y]); }

int Bsx(int St,int Dr)
{
	if ( St==Dr ) return St;
	
	int Mid=(St+Dr)/2;
	if ( Normx[Mid]<Val ) return Bsx(Mid+1,Dr);
	if ( Normx[Mid]>Val ) return Bsx(St,Mid-1);
	
	return Mid;
}

int Bsy(int St,int Dr)
{
	if ( St==Dr ) return St;
	
	int Mid=(St+Dr)/2;
	if ( Normy[Mid]<Val ) return Bsy(Mid+1,Dr);
	if ( Normy[Mid]>Val ) return Bsy(St,Mid-1);
	
	return Mid;
}

int main()
{
	F>>N>>M>>K;
	for (int i=1;i<=K;++i)
	{
		F>>First[i].x>>First[i].y;
		F>>Second[i].x>>Second[i].y;
		F>>Value[i];
		++Second[i].x;
		++Second[i].y;
	}
	
	for (int i=1;i<=K;++i)
	{	
		Coord[++Co]=First[i].x;
		Coord[++Co]=Second[i].x;
	}
	sort(Coord,Coord+Co+1);
	for (int i=1;i<=Co;++i)
		while ( Coord[i]==Coord[i+1] && i<=Co )
			Coord[i++]=0;
	for (int i=1;i<=Co;++i)
		if ( Coord[i] )
			Normx[++Nbrx]=Coord[i];
	
	Co=0;	for (int i=1;i<=K;++i)
	{	
		Coord2[++Co]=First[i].y;
		Coord2[++Co]=Second[i].y;
	}
	Coord2[Co+1]=0;
	sort(Coord2,Coord2+Co+1);
	for (int i=1;i<=Co;++i)
		while ( Coord2[i]==Coord2[i+1] && i<=Co )
			Coord2[i++]=0;
	for (int i=1;i<=Co;++i)
		if ( Coord2[i] )
			Normy[++Nbry]=Coord2[i];
	
	for (int i=1;i<=K;++i)
	{
		Val=First[i].x;
		First[i].x=Bsx(1,Nbrx);
		Val=First[i].y;
		First[i].y=Bsy(1,Nbry);
		Val=Second[i].x;
		Second[i].x=Bsx(1,Nbrx);
		Val=Second[i].y;
		Second[i].y=Bsy(1,Nbry);
	}
	
	for (int i=1;i<=K;++i)
	{
		Mat[First[i].x][First[i].y]+=Value[i];
		Mat[Second[i].x][Second[i].y]+=Value[i];
		Mat[First[i].x][Second[i].y]-=Value[i];
		Mat[Second[i].x][First[i].y]-=Value[i];
	}
	
	for (int i=1;i<=Nbrx;++i)
		for (int j=1;j<=Nbry;++j)
			Max=max(Mat[i][j]=Mat[i][j-1]+Mat[i-1][j]-Mat[i-1][j-1]+Mat[i][j],Max);
	
	Normx[Nbrx+1]=Normx[Nbrx]+1;
	Normx[0]=Normx[Nbrx]-1;
	Normy[Nbry+1]=Normy[Nbry]+1;
	Normy[0]=Normy[Nbry]-1;
	for (int i=1;i<=Nbrx;++i)
		for (int j=1;j<=Nbry;++j)
			Arie+=( Mat[i][j]==Max ) ? Calc(i,j) : 0;
	
	G<<Max<<' '<<Arie<<'\n';
}